My Project
gengftables-conway.cc
Go to the documentation of this file.
1 /* emacs edit mode for this file is -*- C++ -*- */
2 
3 /**
4  *
5  * @file gengftables-conway.cc
6  *
7  * generate addition tables used by Factory
8  * to calculate in GF(q).
9  *
10  * @note This may take quite a while ...
11  *
12 **/
13 
14 
15 #include "config.h"
16 
17 
18 #ifdef HAVE_IOSTREAM
19 #include <iostream>
20 #include <fstream>
21 #include <strstream>
22 #include <string>
23 #else
24 #include <iostream>
25 #include <fstream>
26 #include <strstream>
27 #include <string>
28 #endif
29 
30 
31 #include <stdlib.h>
32 
33 #include "cf_assert.h"
34 #include "gf_tabutil.h"
35 #include "cf_algorithm.h"
36 #include "cf_iter.h"
37 
38 using namespace std;
39 
40 int gf_tab_numdigits62 ( int q );
41 /**
42  *
43  * constants.
44  *
45  * maxtable: maximal size of a gf_table
46  *
47 **/
48 const int maxtable = 65536;
49 
50 /**
51  * primes, primes_len:
52  * used to step through possible extensions
53 **/
54 const int primes_len = 54;
55 
56 /**
57  * primes, primes_len:
58  * used to step through possible extensions
59 **/
60 STATIC_VAR unsigned short primes [] =
61 {
62  2, 3, 5, 7, 11, 13, 17, 19,
63  23, 29, 31, 37, 41, 43, 47, 53,
64  59, 61, 67, 71, 73, 79, 83, 89,
65  97, 101, 103, 107, 109, 113, 127, 131,
66  137, 139, 149, 151, 157, 163, 167, 173,
67  179, 181, 191, 193, 197, 199, 211, 223,
68  227, 229, 233, 239, 241, 251
69 };
70 
71 /** bool isIrreducible ( const CanonicalForm & f )
72  *
73  * isIrreducible() - return true iff f is irreducible.
74  *
75 **/
76 bool
78 {
79  CFFList F = factorize( f );
80  if (F.getFirst().factor().inCoeffDomain())
81  F.removeFirst();
82  return F.length() == 1 && F.getFirst().exp() == 1;
83 }
84 
85 /** int exponent ( const CanonicalForm & f, int q )
86  *
87  * exponent() - return e > 0 such that x^e == 1 mod f.
88  *
89  * q: upper limit for e (?)
90  *
91 **/
92 int
93 exponent ( const CanonicalForm & f, int q )
94 {
95  Variable x = f.mvar();
96  int e = 1;
98  while ( e <= q && ! prod.isOne() ) {
99  e++;
100  prod = ( prod * x ) % f;
101  }
102  return e;
103 }
104 
105 /** bool findGenRec ( int d, int n, int q, const CanonicalForm & m, const Variable & x, CanonicalForm & result )
106  *
107  * findGenRec() - find a generator of GF(q).
108  *
109  * Returns true iff result is a valid generator.
110  *
111  * d: degree of extension
112  * q: the q in GF(q) (q == p^d)
113  * x: generator should be a poly in x
114  * n, m: used to step recursively through all polys in FF(p)
115  * Initially, n == d and m == 0. If 0 <= n <= d we are
116  * in the process of building m, if n < 0 we built m and
117  * may test whether it generates GF(q).
118  * result: generator found
119  *
120  * i: used to step through GF(p)
121  * p: current characteristic
122  *
123 **/
124 bool
125 findGenRec ( int d, int n, int q,
126  const CanonicalForm & m, const Variable & x,
128 {
129  int i, p = getCharacteristic();
130  if ( n < 0 ) {
131  cerr << "."; cerr.flush();
132  // check whether m is irreducible
133  if ( isIrreducible( m ) ) {
134  cerr << "*"; cerr.flush();
135  // check whether m generates multiplicative group
136  if ( exponent( m, q ) == q - 1 ) {
137  result = m;
138  return true;
139  }
140  else
141  return false;
142  }
143  else
144  return false;
145  }
146  // for each monomial x^0, ..., x^n, ..., x^d, try all possible coefficients
147  else if ( n == d || n == 0 ) {
148  // we want to have a leading coefficient and a constant term,
149  // so start with coefficient >= 1
150  for ( i = 1; i < p; i++ )
151  if ( findGenRec( d, n-1, q, m + i * power( x, n ), x, result ) )
152  return true;
153  }
154  else {
155  for ( i = 0; i < p; i++ )
156  if ( findGenRec( d, n-1, q, m + i * power( x, n ), x, result ) )
157  return true;
158  }
159  return false;
160 }
161 
162 /** CanonicalForm findGen ( int d, int q )
163  *
164  * findGen() - find and return a generator of GF(q).
165  *
166  * d: degree of extension
167  * q: the q in GF(q)
168  *
169 **/
171 findGen ( int d, int q )
172 {
173  Variable x( 1 );
175  cerr << "testing p = " << getCharacteristic() << ", d = " << d << " ... ";
176  cerr.flush();
177  bool ok = findGenRec( d, d, q, 0, x, result );
178  cerr << endl;
179  if ( ! ok )
180  return 0;
181  else
182  return result;
183 }
184 
185 /** void printTable ( int d, int q, CanonicalForm mipo )
186  *
187  * printTable - print +1 table of field GF(q).
188  *
189  * d: degree of extension
190  * q: the q in GF(q)
191  * mipo: the minimal polynomial of the extension
192  *
193  * p: current characteristic
194  *
195 **/
196 void
197 printTable ( int d, int q, CanonicalForm mipo )
198 {
199  int i, p = getCharacteristic();
200 
201  // open file to write to
202  ostrstream fname;
203  fname << "gftables/" << q << '\0';
204  char * fn = fname.str();
205  ofstream outfile;
206  outfile.open( fn, ios::out );
207  STICKYASSERT1( outfile, "can not open GF(q) table %s for writing", fn );
208  delete fn;
209 
210  cerr << "mipo = " << mipo << ": ";
211  cerr << "generating multiplicative group ... ";
212  cerr.flush();
213 
215  Variable x( 1 );
216 
217  // fill T with powers of x
218  T[0] = 1;
219  for ( i = 1; i < q; i++ )
220  T[i] = ( T[i-1] * x ) % mipo;
221 
222  cerr << "generating addition table ... ";
223  cerr.flush();
224 
225  // brute force method
226  int * table = new int[maxtable];
228 
229  for ( i = 0; i < q; i++ ) {
230  f = T[i] + 1;
231  int j = 0;
232  while ( j < q && T[j] != f ) j++;
233  table[i] = j;
234  }
235 
236  cerr << "writing table ... ";
237  cerr.flush();
238 
239  outfile << "@@ factory GF(q) table @@" << endl;
240  outfile << p << " " << d << " " << mipo << "; ";
241 
242  // print simple reprenstation of mipo
243  outfile << d;
244  CFIterator MiPo = mipo;
245  for ( i = d; MiPo.hasTerms(); i--, MiPo++ ) {
246  int exp;
247  for ( exp = MiPo.exp(); exp < i; i-- )
248  outfile << " 0";
249  outfile << " " << MiPo.coeff();
250  }
251  // since mipo is irreducible, it has a constant term,
252  // so i == 0 at this point
253  outfile << endl;
254 
255  int m = gf_tab_numdigits62( q );
256  char * outstr = new char[30*m+1];
257  outstr[30*m] = '\0';
258  i = 1;
259  while ( i < q ) {
260  int k = 0;
261  char * sptr = outstr;
262  while ( i < q && k < 30 ) {
263  convert62( table[i], m, sptr );
264  sptr += m;
265  k++; i++;
266  }
267  while ( k < 30 ) {
268  convert62( 0, m, sptr );
269  sptr += m;
270  k++;
271  }
272  outfile << outstr << endl;
273  }
274  outfile.close();
275 
276  delete [] outstr;
277  delete [] T;
278  delete [] table;
279 
280  cerr << endl;
281 }
282 
283 /**
284  * The new function for getting the minimal polynomials.
285  * It uses the Conway polynomials.
286  * It reads the polynomials from a file.
287  * The file contains all polynomials with p^k <= 2^16
288  * but currently only polynomials with p^k <= 2^14 are used.
289 **/
290 static CanonicalForm findGenNew(int n, ///< n is the exponent
291  int q ///< parameter q is not used. It is added to respect the old version
292  )
293 {
294  CanonicalForm conway = 0;
295  Variable x( 1 );
296  int p = getCharacteristic();
297  int ntmp,ptmp,pos1,pos2,ii;
298  string ns, ps;
299  string LineSe,coef,PC;
300  int flag=1;
301  ifstream in("./ConwayList.txt");
302  getline(in,LineSe); // For the first line
303 
304  string err="END"; //to check if we are at the end of the file
305  while((flag) && (err != LineSe))
306  {
307  getline(in,LineSe); //for the line: allConwayPolynomials := [
308  if(LineSe == err){
309  break;
310  }
311  pos1 = LineSe.find( ",", 0 );
312  pos2 = LineSe.find( ",", pos1 + 1); // we check where are the "," to now p and n of this line
313  ps = LineSe.substr(0, pos1);
314  ns = LineSe.substr(pos1 + 1,pos2 - pos1);
315  ptmp = atoi(ps.c_str()); //we have the value of p and n of these line
316  ntmp = atoi(ns.c_str());
317 
318  if((ntmp==n)&&(ptmp==p)){flag=0;} // we check if they are our p and n to stop the search
319 
320  }
321 
322  if (err==LineSe) // If the Conway Polynomial is not in the list, there is an error.
323  {
324  //cout << "Error: This Conway polinomial is not in the list" << endl;
325  return(0);
326  }
327 
328  // Read the polynomial from the file
329  pos1 = pos2 + 1;
330  pos2 = LineSe.find(",", pos1 + 1);
331  conway = atoi(LineSe.substr(pos1, pos2 - pos1).c_str()); // value of the constant term in PC=Conway Polynomial
332  pos1 = pos2;
333  pos2 = LineSe.find(",", pos1 + 1);
334 
335  for(ii = 2; ii <= n; ii++)
336  {
337  coef = LineSe.substr(pos1 + 1,pos2 - pos1 - 1); //Coefficient of the monomial of degree ii-1
338  if(coef != "0")
339  {
340  conway = conway + atoi(coef.c_str()) * power(x, ii - 1) ; //We add this monomial to the Conway Polynomial
341  }
342  pos1 = pos2;
343  pos2 = LineSe.find( ",", pos1+1);
344  }
345 
346  pos2 = LineSe.find( ",END", pos1 + 1); // To obtain the last coefficient we search "END" instead of ","
347  coef = LineSe.substr(pos1 + 1,pos2 - pos1 - 1);
348  conway = conway + atoi(coef.c_str()) * power(x, ii - 1) ; //We add the last monomial to the Conway Polynomial
349 
350  in.close();
351 
352  return(conway);
353 
354 }
355 
356 
357 int
359 {
360  int i, p, q, n;
361  for ( i = 0; i < primes_len; i++ ) {
362  p = primes[i];
363  q = p;
364  n = 1;
365  setCharacteristic( p );
366  while ( q < maxtable ) {
367  CanonicalForm f = findGenNew( n, q );
368  ASSERT( f != 0, "no generator found" );
369  printTable( n, q, f );
370  n++; q *= p;
371  }
372  }
373 }
374 
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
void FACTORY_PUBLIC setCharacteristic(int c)
Definition: cf_char.cc:28
int FACTORY_PUBLIC getCharacteristic()
Definition: cf_char.cc:70
int m
Definition: cfEzgcd.cc:128
int i
Definition: cfEzgcd.cc:132
int k
Definition: cfEzgcd.cc:99
Variable x
Definition: cfModGcd.cc:4082
int p
Definition: cfModGcd.cc:4078
declarations of higher level algorithms.
CFFList FACTORY_PUBLIC factorize(const CanonicalForm &f, bool issqrfree=false)
factorization over or
Definition: cf_factor.cc:405
assertions for Factory
#define STICKYASSERT1(expression, message, parameter1)
Definition: cf_assert.h:66
#define ASSERT(expression, message)
Definition: cf_assert.h:99
Iterators for CanonicalForm's.
FILE * f
Definition: checklibs.c:9
class to iterate through CanonicalForm's
Definition: cf_iter.h:44
CF_NO_INLINE int exp() const
get the current exponent
CF_NO_INLINE CanonicalForm coeff() const
get the current coefficient
CF_NO_INLINE int hasTerms() const
check if iterator has reached the end of CanonicalForm
factory's main class
Definition: canonicalform.h:86
T getFirst() const
Definition: ftmpl_list.cc:279
void removeFirst()
Definition: ftmpl_list.cc:287
int length() const
Definition: ftmpl_list.cc:273
factory's class for variables
Definition: factory.h:127
return result
Definition: facAbsBiFact.cc:75
CanonicalForm mipo
Definition: facAlgExt.cc:57
int j
Definition: facHensel.cc:110
fq_nmod_poly_t prod
Definition: facHensel.cc:100
const int maxtable
constants.
int exponent(const CanonicalForm &f, int q)
int exponent ( const CanonicalForm & f, int q )
int gf_tab_numdigits62(int q)
Definition: gf_tabutil.cc:12
bool isIrreducible(const CanonicalForm &f)
bool isIrreducible ( const CanonicalForm & f )
CanonicalForm findGen(int d, int q)
CanonicalForm findGen ( int d, int q )
bool findGenRec(int d, int n, int q, const CanonicalForm &m, const Variable &x, CanonicalForm &result)
bool findGenRec ( int d, int n, int q, const CanonicalForm & m, const Variable & x,...
void printTable(int d, int q, CanonicalForm mipo)
void printTable ( int d, int q, CanonicalForm mipo )
STATIC_VAR unsigned short primes[]
primes, primes_len: used to step through possible extensions
int main()
const int primes_len
primes, primes_len: used to step through possible extensions
static CanonicalForm findGenNew(int n, int q)
The new function for getting the minimal polynomials.
void convert62(int i, int n, char *p)
Definition: gf_tabutil.cc:32
utility functions to access GF Tables
#define STATIC_VAR
Definition: globaldefs.h:7
STATIC_VAR jList * T
Definition: janet.cc:30
gmp_float exp(const gmp_float &a)
Definition: mpr_complex.cc:357