My Project
Functions | Variables
gengftables-conway.cc File Reference

generate addition tables used by Factory to calculate in GF(q). More...

#include "config.h"
#include <iostream>
#include <fstream>
#include <strstream>
#include <string>
#include <stdlib.h>
#include "cf_assert.h"
#include "gf_tabutil.h"
#include "cf_algorithm.h"
#include "cf_iter.h"

Go to the source code of this file.

Functions

bool isIrreducible (const CanonicalForm &f)
 bool isIrreducible ( const CanonicalForm & f ) More...
 
int exponent (const CanonicalForm &f, int q)
 int exponent ( const CanonicalForm & f, int q ) More...
 
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 ) More...
 
CanonicalForm findGen (int d, int q)
 CanonicalForm findGen ( int d, int q ) More...
 
void printTable (int d, int q, CanonicalForm mipo)
 void printTable ( int d, int q, CanonicalForm mipo ) More...
 
static CanonicalForm findGenNew (int n, int q)
 The new function for getting the minimal polynomials. More...
 
int main ()
 

Variables

const int maxtable = 65536
 constants. More...
 
const int primes_len = 54
 primes, primes_len: used to step through possible extensions More...
 
STATIC_VAR unsigned short primes []
 primes, primes_len: used to step through possible extensions More...
 

Detailed Description

generate addition tables used by Factory to calculate in GF(q).

Note
This may take quite a while ...

Definition in file gengftables-conway.cc.

Function Documentation

◆ exponent()

int exponent ( const CanonicalForm f,
int  q 
)

int exponent ( const CanonicalForm & f, int q )

exponent() - return e > 0 such that x^e == 1 mod f.

q: upper limit for e (?)

Definition at line 92 of file gengftables-conway.cc.

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}
Variable x
Definition: cfModGcd.cc:4084
f
Definition: cfModGcd.cc:4083
factory's main class
Definition: canonicalform.h:86
factory's class for variables
Definition: factory.h:134
fq_nmod_poly_t prod
Definition: facHensel.cc:100

◆ findGen()

CanonicalForm findGen ( int  d,
int  q 
)

CanonicalForm findGen ( int d, int q )

findGen() - find and return a generator of GF(q).

d: degree of extension q: the q in GF(q)

Definition at line 170 of file gengftables-conway.cc.

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}
int FACTORY_PUBLIC getCharacteristic()
Definition: cf_char.cc:70
return result
Definition: facAbsBiFact.cc:75
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,...

◆ findGenNew()

static CanonicalForm findGenNew ( int  n,
int  q 
)
static

The new function for getting the minimal polynomials.

It uses the Conway polynomials. It reads the polynomials from a file. The file contains all polynomials with p^k <= 2^16 but currently only polynomials with p^k <= 2^14 are used.

Parameters
nn is the exponent
qparameter q is not used. It is added to respect the old version

Definition at line 289 of file gengftables-conway.cc.

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}
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
int p
Definition: cfModGcd.cc:4080

◆ findGenRec()

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 )

findGenRec() - find a generator of GF(q).

Returns true iff result is a valid generator.

d: degree of extension q: the q in GF(q) (q == p^d) x: generator should be a poly in x n, m: used to step recursively through all polys in FF(p) Initially, n == d and m == 0. If 0 <= n <= d we are in the process of building m, if n < 0 we built m and may test whether it generates GF(q). result: generator found

i: used to step through GF(p) p: current characteristic

Definition at line 124 of file gengftables-conway.cc.

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}
int m
Definition: cfEzgcd.cc:128
int i
Definition: cfEzgcd.cc:132
int exponent(const CanonicalForm &f, int q)
int exponent ( const CanonicalForm & f, int q )
bool isIrreducible(const CanonicalForm &f)
bool isIrreducible ( const CanonicalForm & f )

◆ isIrreducible()

bool isIrreducible ( const CanonicalForm f)

bool isIrreducible ( const CanonicalForm & f )

isIrreducible() - return true iff f is irreducible.

Definition at line 76 of file gengftables-conway.cc.

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}
CFFList FACTORY_PUBLIC factorize(const CanonicalForm &f, bool issqrfree=false)
factorization over or
Definition: cf_factor.cc:405
T getFirst() const
Definition: ftmpl_list.cc:279
void removeFirst()
Definition: ftmpl_list.cc:287
int length() const
Definition: ftmpl_list.cc:273

◆ main()

int main ( )

Definition at line 357 of file gengftables-conway.cc.

358{
359 int i, p, q, n;
360 for ( i = 0; i < primes_len; i++ ) {
361 p = primes[i];
362 q = p;
363 n = 1;
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}
void FACTORY_PUBLIC setCharacteristic(int c)
Definition: cf_char.cc:28
#define ASSERT(expression, message)
Definition: cf_assert.h:99
const int maxtable
constants.
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
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.

◆ printTable()

void printTable ( int  d,
int  q,
CanonicalForm  mipo 
)

void printTable ( int d, int q, CanonicalForm mipo )

printTable - print +1 table of field GF(q).

d: degree of extension q: the q in GF(q) mipo: the minimal polynomial of the extension

p: current characteristic

Definition at line 196 of file gengftables-conway.cc.

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}
int k
Definition: cfEzgcd.cc:99
#define STICKYASSERT1(expression, message, parameter1)
Definition: cf_assert.h:66
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
CanonicalForm mipo
Definition: facAlgExt.cc:57
int j
Definition: facHensel.cc:110
void convert62(int i, int n, char *p)
Definition: gf_tabutil.cc:32
int gf_tab_numdigits62(int q)
Definition: gf_tabutil.cc:12
STATIC_VAR jList * T
Definition: janet.cc:30
gmp_float exp(const gmp_float &a)
Definition: mpr_complex.cc:357

Variable Documentation

◆ maxtable

const int maxtable = 65536

constants.

maxtable: maximal size of a gf_table

Definition at line 47 of file gengftables-conway.cc.

◆ primes

STATIC_VAR unsigned short primes[]
Initial value:
=
{
2, 3, 5, 7, 11, 13, 17, 19,
23, 29, 31, 37, 41, 43, 47, 53,
59, 61, 67, 71, 73, 79, 83, 89,
97, 101, 103, 107, 109, 113, 127, 131,
137, 139, 149, 151, 157, 163, 167, 173,
179, 181, 191, 193, 197, 199, 211, 223,
227, 229, 233, 239, 241, 251
}

primes, primes_len: used to step through possible extensions

Definition at line 59 of file gengftables-conway.cc.

◆ primes_len

const int primes_len = 54

primes, primes_len: used to step through possible extensions

Definition at line 53 of file gengftables-conway.cc.