Loading...
Searching...
No Matches
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

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

## Variables

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

## 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 93 of file gengftables-conway.cc.

{
Variable x = f.mvar();
int e = 1;
CanonicalForm prod = x;
while ( e <= q && ! prod.isOne() ) {
e++;
prod = ( prod * x ) % f;
}
return e;
}
x
Variable x
Definition cfModGcd.cc:4090
f
FILE * f
Definition checklibs.c:9
CanonicalForm
factory's main class
Definition canonicalform.h:86
Variable
factory's class for variables
Definition factory.h:127
prod
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 171 of file gengftables-conway.cc.

{
Variable x( 1 );
CanonicalForm result;
cerr << "testing p = " << getCharacteristic() << ", d = " << d << " ... ";
cerr.flush();
bool ok = findGenRec( d, d, q, 0, x, result );
cerr << endl;
if ( ! ok )
return 0;
else
return result;
}
getCharacteristic
int FACTORY_PUBLIC getCharacteristic()
Definition cf_char.cc:70
result
return result
Definition facAbsBiFact.cc:76
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,...
Definition gengftables-conway.cc:125

## findGenNew()

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

  n | n is the exponent
  q | parameter q is not used. It is added to respect the old version

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

{
CanonicalForm conway = 0;
Variable x( 1 );
int p = getCharacteristic();
int ntmp,ptmp,pos1,pos2,ii;
string ns, ps;
string LineSe,coef,PC;
int flag=1;
ifstream in("./ConwayList.txt");
getline(in,LineSe); // For the first line
string err="END"; //to check if we are at the end of the file
while((flag) && (err != LineSe))
{
getline(in,LineSe); //for the line: allConwayPolynomials := [
if(LineSe == err){
break;
}
pos1 = LineSe.find( ",", 0 );
pos2 = LineSe.find( ",", pos1 + 1); // we check where are the "," to now p and n of this line
ps = LineSe.substr(0, pos1);
ns = LineSe.substr(pos1 + 1,pos2 - pos1);
ptmp = atoi(ps.c_str()); //we have the value of p and n of these line
ntmp = atoi(ns.c_str());
if((ntmp==n)&&(ptmp==p)){flag=0;} // we check if they are our p and n to stop the search
}
if (err==LineSe) // If the Conway Polynomial is not in the list, there is an error.
{
//cout << "Error: This Conway polinomial is not in the list" << endl;
return(0);
}
// Read the polynomial from the file
pos1 = pos2 + 1;
pos2 = LineSe.find(",", pos1 + 1);
conway = atoi(LineSe.substr(pos1, pos2 - pos1).c_str()); // value of the constant term in PC=Conway Polynomial
pos1 = pos2;
pos2 = LineSe.find(",", pos1 + 1);
for(ii = 2; ii <= n; ii++)
{
coef = LineSe.substr(pos1 + 1,pos2 - pos1 - 1); //Coefficient of the monomial of degree ii-1
if(coef != "0")
{
conway = conway + atoi(coef.c_str()) * power(x, ii - 1) ; //We add this monomial to the Conway Polynomial
}
pos1 = pos2;
pos2 = LineSe.find( ",", pos1+1);
}
pos2 = LineSe.find( ",END", pos1 + 1); // To obtain the last coefficient we search "END" instead of ","
coef = LineSe.substr(pos1 + 1,pos2 - pos1 - 1);
conway = conway + atoi(coef.c_str()) * power(x, ii - 1) ; //We add the last monomial to the Conway Polynomial
in.close();
return(conway);
}
power
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
Definition canonicalform.cc:1896
p
int p
Definition cfModGcd.cc:4086

## 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 125 of file gengftables-conway.cc.

{
int i, p = getCharacteristic();
if ( n < 0 ) {
cerr << "."; cerr.flush();
// check whether m is irreducible
if ( isIrreducible( m ) ) {
cerr << "*"; cerr.flush();
// check whether m generates multiplicative group
if ( exponent( m, q ) == q - 1 ) {
result = m;
return true;
}
else
return false;
}
else
return false;
}
// for each monomial x^0, ..., x^n, ..., x^d, try all possible coefficients
else if ( n == d || n == 0 ) {
// we want to have a leading coefficient and a constant term,
// so start with coefficient >= 1
for ( i = 1; i < p; i++ )
if ( findGenRec( d, n-1, q, m + i * power( x, n ), x, result ) )
return true;
}
else {
for ( i = 0; i < p; i++ )
if ( findGenRec( d, n-1, q, m + i * power( x, n ), x, result ) )
return true;
}
return false;
}
m
int m
Definition cfEzgcd.cc:128
i
int i
Definition cfEzgcd.cc:132
isIrreducible
bool isIrreducible(const CanonicalForm &f)
bool isIrreducible ( const CanonicalForm & f )
Definition gengftables-conway.cc:77
exponent
#define exponent
Definition interpolation.cc:31

## gf_tab_numdigits62()

int gf_tab_numdigits62 | ( | int | q | ) |

Definition at line 12 of file gf_tabutil.cc.

{
if ( q < 62 )
return 1;
else if ( q < 62*62 )
return 2;
else
return 3;
}

## isIrreducible()

bool isIrreducible | ( | const CanonicalForm & | f | ) |

bool isIrreducible ( const CanonicalForm & f )

isIrreducible() - return true iff f is irreducible.

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

{
CFFList F = factorize( f );
if (F.getFirst().factor().inCoeffDomain())
F.removeFirst();
return F.length() == 1 && F.getFirst().exp() == 1;
}
CFFList
List< CFFactor > CFFList
Definition canonicalform.h:393
factorize
CFFList FACTORY_PUBLIC factorize(const CanonicalForm &f, bool issqrfree=false)
factorization over or
Definition cf_factor.cc:409
CanonicalForm::inCoeffDomain
bool inCoeffDomain() const
Definition canonicalform.cc:122
Factor::exp
int exp() const
Definition ftmpl_factor.h:31
Factor::factor
T factor() const
Definition ftmpl_factor.h:30
List::getFirst
T getFirst() const
Definition ftmpl_list.cc:279
List::removeFirst
void removeFirst()
Definition ftmpl_list.cc:287
List::length
int length() const
Definition ftmpl_list.cc:273

## main()

int main | ( |  | ) |

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

{
int i, p, q, n;
for ( i = 0; i < primes_len; i++ ) {
p = primes[i];
q = p;
n = 1;
setCharacteristic( p );
while ( q < maxtable ) {
CanonicalForm f = findGenNew( n, q );
ASSERT( f != 0, "no generator found" );
printTable( n, q, f );
n++; q *= p;
}
}
}
setCharacteristic
void FACTORY_PUBLIC setCharacteristic(int c)
Definition cf_char.cc:28
ASSERT
#define ASSERT(expression, message)
Definition cf_assert.h:99
maxtable
const int maxtable
constants.
Definition gengftables-conway.cc:48
printTable
void printTable(int d, int q, CanonicalForm mipo)
void printTable ( int d, int q, CanonicalForm mipo )
Definition gengftables-conway.cc:197
primes
STATIC_VAR unsigned short primes[]
primes, primes_len: used to step through possible extensions
Definition gengftables-conway.cc:60
primes_len
const int primes_len
primes, primes_len: used to step through possible extensions
Definition gengftables-conway.cc:54
findGenNew
static CanonicalForm findGenNew(int n, int q)
The new function for getting the minimal polynomials.
Definition gengftables-conway.cc:290

## 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 197 of file gengftables-conway.cc.

{
int i, p = getCharacteristic();
// open file to write to
ostrstream fname;
fname << "gftables/" << q << '\0';
char * fn = fname.str();
ofstream outfile;
outfile.open( fn, ios::out );
STICKYASSERT1( outfile, "can not open GF(q) table %s for writing", fn );
delete fn;
cerr << "mipo = " << mipo << ": ";
cerr << "generating multiplicative group ... ";
cerr.flush();
CanonicalForm * T = new CanonicalForm[maxtable];
Variable x( 1 );
// fill T with powers of x
T[0] = 1;
for ( i = 1; i < q; i++ )
T[i] = ( T[i-1] * x ) % mipo;
cerr << "generating addition table ... ";
cerr.flush();
// brute force method
int * table = new int[maxtable];
CanonicalForm f;
for ( i = 0; i < q; i++ ) {
f = T[i] + 1;
int j = 0;
while ( j < q && T[j] != f ) j++;
table[i] = j;
}
cerr << "writing table ... ";
cerr.flush();
outfile << "@@ factory GF(q) table @@" << endl;
outfile << p << " " << d << " " << mipo << "; ";
// print simple reprenstation of mipo
outfile << d;
CFIterator MiPo = mipo;
for ( i = d; MiPo.hasTerms(); i--, MiPo++ ) {
int exp;
for ( exp = MiPo.exp(); exp < i; i-- )
outfile << " 0";
outfile << " " << MiPo.coeff();
}
// since mipo is irreducible, it has a constant term,
// so i == 0 at this point
outfile << endl;
int m = gf_tab_numdigits62( q );
char * outstr = new char[30*m+1];
outstr[30*m] = '\0';
i = 1;
while ( i < q ) {
int k = 0;
char * sptr = outstr;
while ( i < q && k < 30 ) {
convert62( table[i], m, sptr );
sptr += m;
k++; i++;
}
while ( k < 30 ) {
convert62( 0, m, sptr );
sptr += m;
k++;
}
outfile << outstr << endl;
}
outfile.close();
delete [] outstr;
delete [] T;
delete [] table;
cerr << endl;
}
k
int k
Definition cfEzgcd.cc:99
STICKYASSERT1
#define STICKYASSERT1(expression, message, parameter1)
Definition cf_assert.h:66
CFIterator
class to iterate through CanonicalForm's
Definition cf_iter.h:44
CFIterator::exp
CF_NO_INLINE int exp() const
get the current exponent
CFIterator::coeff
CF_NO_INLINE CanonicalForm coeff() const
get the current coefficient
CFIterator::hasTerms
CF_NO_INLINE int hasTerms() const
check if iterator has reached the end of CanonicalForm
mipo
CanonicalForm mipo
Definition facAlgExt.cc:57
j
int j
Definition facHensel.cc:110
gf_tab_numdigits62
int gf_tab_numdigits62(int q)
Definition gf_tabutil.cc:12
convert62
void convert62(int i, int n, char *p)
Definition gf_tabutil.cc:32
T
STATIC_VAR jList * T
Definition janet.cc:30
exp
gmp_float exp(const gmp_float &a)
Definition mpr_complex.cc:349

## Variable Documentation

## maxtable

const int maxtable = 65536

constants.

maxtable: maximal size of a gf_table

Definition at line 48 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 60 of file gengftables-conway.cc.

{
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_len

const int primes_len = 54

primes, primes_len: used to step through possible extensions

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