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