source: git/factory/gengftables-conway.cc @ d67fcad

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