source: git/factory/gengftables-conway.cc @ 362fc67

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