Loading...
Searching...
No Matches
gengftables-conway.cc
Go to the documentation of this file.
/* emacs edit mode for this file is -*- C++ -*- */
/**
*
* @file gengftables-conway.cc
*
* generate addition tables used by Factory
* to calculate in GF(q).
*
* @note This may take quite a while ...
*
**/
#include "config.h"
#ifdef HAVE_IOSTREAM
#include <iostream>
#include <fstream>
#include <strstream>
#include <string>
#else
#include <iostream>
#include <fstream>
#include <strstream>
#include <string>
#endif
#include <stdlib.h>
#include "cf_assert.h"
#include "gf_tabutil.h"
#include "cf_algorithm.h"
#include "cf_iter.h"
using namespace std;
int gf_tab_numdigits62 ( int q );
/**
*
* constants.
*
* maxtable: maximal size of a gf_table
*
**/
const int maxtable = 65536;
/**
* primes, primes_len:
* used to step through possible extensions
**/
const int primes_len = 54;
/**
* primes, primes_len:
* used to step through possible extensions
**/
STATIC_VAR unsigned short primes [] =
{
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
};
/** bool isIrreducible ( const CanonicalForm & f )
*
* isIrreducible() - return true iff f is irreducible.
*
**/
bool
isIrreducible ( const CanonicalForm & f )
{
CFFList F = factorize( f );
if (F.getFirst().factor().inCoeffDomain())
F.removeFirst();
return F.length() == 1 && F.getFirst().exp() == 1;
}
/** int exponent ( const CanonicalForm & f, int q )
*
* exponent() - return e > 0 such that x^e == 1 mod f.
*
* q: upper limit for e (?)
*
**/
int
exponent ( const CanonicalForm & f, int q )
{
Variable x = f.mvar();
int e = 1;
CanonicalForm prod = x;
while ( e <= q && ! prod.isOne() ) {
e++;
prod = ( prod * x ) % f;
}
return e;
}
/** 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
*
**/
bool
findGenRec ( int d, int n, int q,
const CanonicalForm & m, const Variable & x,
CanonicalForm & result )
{
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;
}
/** 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)
*
**/
CanonicalForm
findGen ( int d, int q )
{
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;
}
/** 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
*
**/
void
printTable ( int d, int q, CanonicalForm mipo )
{
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;
}
/**
* 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.
**/
static CanonicalForm findGenNew(int n, ///< n is the exponent
int q ///< parameter q is not used. It is added to respect the old version
)
{
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);
}
int
main()
{
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;
}
}
}
power
CanonicalForm power(const CanonicalForm &f, int n)
exponentiation
Definition canonicalform.cc:1896
setCharacteristic
void FACTORY_PUBLIC setCharacteristic(int c)
Definition cf_char.cc:28
CFFList
List< CFFactor > CFFList
Definition canonicalform.h:393
getCharacteristic
int FACTORY_PUBLIC getCharacteristic()
Definition cf_char.cc:70
m
int m
Definition cfEzgcd.cc:128
i
int i
Definition cfEzgcd.cc:132
k
int k
Definition cfEzgcd.cc:99
x
Variable x
Definition cfModGcd.cc:4090
p
int p
Definition cfModGcd.cc:4086
cf_algorithm.h
declarations of higher level algorithms.
factorize
CFFList FACTORY_PUBLIC factorize(const CanonicalForm &f, bool issqrfree=false)
factorization over or
Definition cf_factor.cc:409
cf_assert.h
assertions for Factory
STICKYASSERT1
#define STICKYASSERT1(expression, message, parameter1)
Definition cf_assert.h:66
ASSERT
#define ASSERT(expression, message)
Definition cf_assert.h:99
cf_iter.h
Iterators for CanonicalForm's.
f
FILE * f
Definition checklibs.c:9
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
CanonicalForm
factory's main class
Definition canonicalform.h:86
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
Variable
factory's class for variables
Definition factory.h:127
result
return result
Definition facAbsBiFact.cc:76
mipo
CanonicalForm mipo
Definition facAlgExt.cc:57
j
int j
Definition facHensel.cc:110
prod
fq_nmod_poly_t prod
Definition facHensel.cc:100
maxtable
const int maxtable
constants.
Definition gengftables-conway.cc:48
gf_tab_numdigits62
int gf_tab_numdigits62(int q)
Definition gf_tabutil.cc:12
isIrreducible
bool isIrreducible(const CanonicalForm &f)
bool isIrreducible ( const CanonicalForm & f )
Definition gengftables-conway.cc:77
findGen
CanonicalForm findGen(int d, int q)
CanonicalForm findGen ( int d, int q ).
Definition gengftables-conway.cc:171
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
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
main
int main()
Definition gengftables-conway.cc:358
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
convert62
void convert62(int i, int n, char *p)
Definition gf_tabutil.cc:32
gf_tabutil.h
utility functions to access GF Tables
STATIC_VAR
#define STATIC_VAR
Definition globaldefs.h:7
exponent
#define exponent
Definition interpolation.cc:31
T
STATIC_VAR jList * T
Definition janet.cc:30
exp
gmp_float exp(const gmp_float &a)
Definition mpr_complex.cc:349