source: git/factory/gengftables-conway.cc @ 502f5f6

spielwiese
Last change on this file since 502f5f6 was 502f5f6, checked in by Oleksandr Motsak <motsak@…>, 13 years ago
CHG: trying to fix compilation problems due to factory.h
  • Property mode set to 100644
File size: 9.5 KB
Line 
1/* emacs edit mode for this file is -*- C++ -*- */
2/* $Id$ */
3
4//{{{ docu
5//
6// gengftables.cc - generate addition tables used by Factory
7//   to calculate in GF(q).
8//
9// Note: This may take quite a while ...
10//
11//}}}
12
13#include "factory.h"
14
15#ifdef HAVE_IOSTREAM
16#include <iostream>
17#include <fstream>
18#include <strstream>
19#include <string>
20#else
21#include <iostream.h>
22#include <fstream.h>
23#include <strstream.h>
24#include <string.h>
25#endif
26
27
28#include <stdlib.h>
29
30
31#include "cf_assert.h"
32#include "gf_tabutil.h"
33
34using namespace std;
35
36int initializeGMP()
37{
38  return 1;
39}
40
41
42//{{{ constants
43//{{{ docu
44//
45// - constants.
46//
47// maxtable: maximal size of a gf_table
48// primes, primes_len:
49//   used to step through possible extensions
50//
51//}}}
52const int maxtable = 65536;
53
54const int primes_len = 54;
55static unsigned short primes [] =
56{
57      2,   3,   5,   7,  11,  13,  17,  19,
58     23,  29,  31,  37,  41,  43,  47,  53,
59     59,  61,  67,  71,  73,  79,  83,  89,
60     97, 101, 103, 107, 109, 113, 127, 131,
61    137, 139, 149, 151, 157, 163, 167, 173,
62    179, 181, 191, 193, 197, 199, 211, 223,
63        227, 229, 233, 239, 241, 251
64};
65//}}}
66
67//{{{ bool isIrreducible ( const CanonicalForm & f )
68//{{{ docu
69//
70// isIrreducible() - return true iff f is irreducible.
71//
72//}}}
73bool
74isIrreducible ( const CanonicalForm & f )
75{
76    CFFList F = factorize( f );
77    return F.length() == 1 && F.getFirst().exp() == 1;
78}
79//}}}
80
81//{{{ int exponent ( const CanonicalForm & f, int q )
82//{{{ docu
83//
84// exponent() - return e > 0 such that x^e == 1 mod f.
85//
86// q: upper limit for e (?)
87//
88//}}}
89int
90exponent ( const CanonicalForm & f, int q )
91{
92    Variable x = f.mvar();
93    int e = 1;
94    CanonicalForm prod = x;
95    while ( e <= q && ! prod.isOne() ) {
96        e++;
97        prod = ( prod * x ) % f;
98    }
99    return e;
100}
101//}}}
102
103//{{{ bool findGenRec ( int d, int n, int q, const CanonicalForm & m, const Variable & x, CanonicalForm & result )
104//{{{ docu
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//}}}
123bool
124findGenRec ( int d, int n, int q,
125             const CanonicalForm & m, const Variable & x,
126             CanonicalForm & result )
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
162//{{{ CanonicalForm findGen ( int d, int q )
163//{{{ docu
164//
165// findGen() - find and return a generator of GF(q).
166//
167// d: degree of extension
168// q: the q in GF(q)
169//
170//}}}
171CanonicalForm
172findGen ( int d, int q )
173{
174    Variable x( 1 );
175    CanonicalForm result;
176    cerr << "testing p = " << getCharacteristic() << ", d = " << d << " ... ";
177    cerr.flush();
178    bool ok = findGenRec( d, d, q, 0, x, result );
179    cerr << endl;
180    if ( ! ok )
181        return 0;
182    else
183        return result;
184}
185//}}}
186
187//{{{ void printTable ( int d, int q, CanonicalForm mipo )
188//{{{ docu
189//
190// printTable - print +1 table of field GF(q).
191//
192// d: degree of extension
193// q: the q in GF(q)
194// mipo: the minimal polynomial of the extension
195//
196// p: current characteristic
197//
198//}}}
199void
200printTable ( int d, int q, CanonicalForm mipo )
201{
202    int i, p = getCharacteristic();
203
204    // open file to write to
205        ostrstream fname;
206    fname << "gftables/gftable." << p << "." << d << '\0';
207    char * fn = fname.str();
208    ofstream outfile;
209    outfile.open( fn, ios::out );
210    STICKYASSERT1( outfile, "can not open GF(q) table %s for writing", fn );
211    delete fn;
212
213    cerr << "mipo = " << mipo << ": ";
214    cerr << "generating multiplicative group ... ";
215    cerr.flush();
216
217    CanonicalForm * T = new CanonicalForm[maxtable];
218    Variable x( 1 );
219
220    // fill T with powers of x
221    T[0] = 1;
222    for ( i = 1; i < q; i++ )
223        T[i] = ( T[i-1] * x ) % mipo;
224
225    cerr << "generating addition table ... ";
226    cerr.flush();
227
228    // brute force method
229    int * table = new int[maxtable];
230    CanonicalForm f;
231
232    for ( i = 0; i < q; i++ ) {
233        f = T[i] + 1;
234        int j = 0;
235        while ( j < q && T[j] != f ) j++;
236        table[i] = j;
237    }
238
239    cerr << "writing table ... ";
240    cerr.flush();
241
242    outfile << "@@ factory GF(q) table @@" << endl;
243    outfile << p << " " << d << " " << mipo << "; ";
244
245    // print simple reprenstation of mipo
246    outfile << d;
247    CFIterator MiPo = mipo;
248    for ( i = d; MiPo.hasTerms(); i--, MiPo++ ) {
249        int exp;
250        for ( exp = MiPo.exp(); exp < i; i-- )
251            outfile << " 0";
252        outfile << " " << MiPo.coeff();
253    }
254    // since mipo is irreducible, it has a constant term,
255    // so i == 0 at this point
256    outfile << endl;
257
258    int m = gf_tab_numdigits62( q );
259    char * outstr = new char[30*m+1];
260    outstr[30*m] = '\0';
261    i = 1;
262    while ( i < q ) {
263        int k = 0;
264        char * sptr = outstr;
265        while ( i < q && k < 30 ) {
266            convert62( table[i], m, sptr );
267            sptr += m;
268            k++; i++;
269        }
270        while ( k < 30 ) {
271            convert62( 0, m, sptr );
272            sptr += m;
273            k++;
274        }
275        outfile << outstr << endl;
276    }
277    outfile.close();
278
279    delete [] outstr;
280    delete [] T;
281    delete [] table;
282
283    cerr << endl;
284}
285//}}}
286
287// The new function for getting the minimal polynomials.
288// It uses the Conway polynomials.
289// It reads the polynomials from a file.
290// The file contains all poynomials with p^k <= 2^16
291// but currently only polynomials with p^k <= 2^14 are used.
292static CanonicalForm findGenNew(int n, int q)
293// n is the exponent
294// parameter q is not used. It is added to respect the old version
295{
296        CanonicalForm conway = 0;
297        Variable x( 1 );
298        int p = getCharacteristic();
299        int ntmp,ptmp,pos1,pos2,ii;
300        string ns, ps;
301        string LineSe,coef,PC;
302        int flag=1;
303        ifstream in("./ConwayList.txt");
304        getline(in,LineSe); // For the first line
305
306        string err="END"; //to check if we are at the end of the file
307        while((flag) && (err != LineSe))
308        {
309                getline(in,LineSe); //for the line: allConwayPolynomials := [
310                if(LineSe == err){
311                        break;
312                }
313                pos1 = LineSe.find( ",", 0 );
314                pos2 = LineSe.find( ",", pos1 + 1);        // we check where are the "," to now p and n of this line
315                ps = LineSe.substr(0, pos1);
316                ns = LineSe.substr(pos1 + 1,pos2 - pos1);
317                ptmp = atoi(ps.c_str());                //we have the value of p and n of these line
318                ntmp = atoi(ns.c_str());
319
320        if((ntmp==n)&&(ptmp==p)){flag=0;}        // we check if they are our p and n to stop the search
321
322        }
323
324        if (err==LineSe) // If the Conway Polynomial is not in the list, there is an error.
325        {
326                //cout << "Error: This Conway polinomial is not in the list" << endl;
327                return(0);
328        }
329
330        // Read the polynomial from the file
331        pos1 = pos2 + 1;
332        pos2 = LineSe.find(",", pos1 + 1);
333        conway = atoi(LineSe.substr(pos1, pos2 - pos1).c_str()); // value of the constant term in PC=Conway Polynomial
334    pos1 = pos2;
335        pos2 = LineSe.find(",", pos1 + 1);
336
337        for(ii = 2; ii <= n; ii++)
338        {
339                coef = LineSe.substr(pos1 + 1,pos2 - pos1 - 1); //Coefficient of the monomial of degree ii-1
340        if(coef != "0")
341                {
342                        conway = conway + atoi(coef.c_str()) * power(x, ii - 1) ; //We add this monomial to the Conway Polynomial
343                }
344                pos1 = pos2;
345                pos2 = LineSe.find( ",", pos1+1);
346        }
347
348        pos2 = LineSe.find( ",END", pos1 + 1); // To obtain the last coefficient we search "END" instead of ","
349        coef = LineSe.substr(pos1 + 1,pos2 - pos1 - 1);
350        conway = conway + atoi(coef.c_str()) * power(x, ii - 1) ; //We add the last monomial to the Conway Polynomial
351
352        in.close();
353
354        return(conway);
355
356}
357
358
359int
360main()
361{
362    int i, p, q, n;
363    for ( i = 0; i < primes_len; i++ ) {
364                p = primes[i];
365                q = p*p;
366                n = 2;
367                setCharacteristic( p );
368                while ( q < maxtable ) {
369                        CanonicalForm f = findGenNew( n, q );
370                        ASSERT( f != 0, "no generator found" );
371                        printTable( n, q, f );
372                        n++; q *= p;
373                }
374    }
375}
376
Note: See TracBrowser for help on using the repository browser.