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 ) 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 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;
}

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;
}

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

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);
 
}

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;
}

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;
}

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;
                }
    }
}

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;
}

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.

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.