source: git/factory/gengftables.cc @ fbb0173

spielwiese
Last change on this file since fbb0173 was efce9a, checked in by mlee <martinlee84@…>, 13 years ago
FIX: genftables
  • Property mode set to 100644
File size: 6.7 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>
19using namespace std;
20#elif defined(HAVE_IOSTREAM_H)
21#include <iostream.h>
22#include <fstream.h>
23#include <strstream.h>
24#endif
25
26#include "cf_assert.h"
27#include "gf_tabutil.h"
28#include "cf_algorithm.h"
29#include "cf_iter.h"
30
31int initializeGMP(){ return 1; }
32
33//{{{ constants
34//{{{ docu
35//
36// - constants.
37//
38// maxtable: maximal size of a gf_table
39// primes, primes_len:
40//   used to step through possible extensions
41//
42//}}}
43const int maxtable = 32767;
44
45const int primes_len = 42;
46static unsigned short primes [] =
47{
48      2,   3,   5,   7,  11,  13,  17,  19,
49     23,  29,  31,  37,  41,  43,  47,  53,
50     59,  61,  67,  71,  73,  79,  83,  89,
51     97, 101, 103, 107, 109, 113, 127, 131,
52    137, 139, 149, 151, 157, 163, 167, 173,
53    179, 181
54};
55//}}}
56
57//{{{ bool isIrreducible ( const CanonicalForm & f )
58//{{{ docu
59//
60// isIrreducible() - return true iff f is irreducible.
61//
62//}}}
63bool
64isIrreducible ( const CanonicalForm & f )
65{
66    CFFList F = factorize( f );
67    return F.length() == 1 && F.getFirst().exp() == 1;
68}
69//}}}
70
71//{{{ int exponent ( const CanonicalForm & f, int q )
72//{{{ docu
73//
74// exponent() - return e > 0 such that x^e == 1 mod f.
75//
76// q: upper limit for e (?)
77//
78//}}}
79int
80exponent ( const CanonicalForm & f, int q )
81{
82    Variable x = f.mvar();
83    int e = 1;
84    CanonicalForm prod = x;
85    while ( e <= q && ! prod.isOne() ) {
86        e++;
87        prod = ( prod * x ) % f;
88    }
89    return e;
90}
91//}}}
92
93//{{{ bool findGenRec ( int d, int n, int q, const CanonicalForm & m, const Variable & x, CanonicalForm & result )
94//{{{ docu
95//
96// findGenRec() - find a generator of GF(q).
97//
98// Returns true iff result is a valid generator.
99//
100// d: degree of extension
101// q: the q in GF(q) (q == p^d)
102// x: generator should be a poly in x
103// n, m: used to step recursively through all polys in FF(p)
104//   Initially, n == d and m == 0.  If 0 <= n <= d we are
105//   in the process of building m, if n < 0 we built m and
106//   may test whether it generates GF(q).
107// result: generator found
108//
109// i: used to step through GF(p)
110// p: current characteristic
111//
112//}}}
113bool
114findGenRec ( int d, int n, int q,
115             const CanonicalForm & m, const Variable & x,
116             CanonicalForm & result )
117{
118    int i, p = getCharacteristic();
119    if ( n < 0 ) {
120        cerr << "."; cerr.flush();
121        // check whether m is irreducible
122        if ( isIrreducible( m ) ) {
123            cerr << "*"; cerr.flush();
124            // check whether m generates multiplicative group
125            if ( exponent( m, q ) == q - 1 ) {
126                result = m;
127                return true;
128            }
129            else
130                return false;
131        }
132        else
133            return false;
134    }
135    // for each monomial x^0, ..., x^n, ..., x^d, try all possible coefficients
136    else  if ( n == d || n == 0 ) {
137        // we want to have a leading coefficient and a constant term,
138        // so start with coefficient >= 1
139        for ( i = 1; i < p; i++ )
140            if ( findGenRec( d, n-1, q, m + i * power( x, n ), x, result ) )
141                return true;
142    }
143    else {
144        for ( i = 0; i < p; i++ )
145            if ( findGenRec( d, n-1, q, m + i * power( x, n ), x, result ) )
146                return true;
147    }
148    return false;
149}
150//}}}
151
152//{{{ CanonicalForm findGen ( int d, int q )
153//{{{ docu
154//
155// findGen() - find and return a generator of GF(q).
156//
157// d: degree of extension
158// q: the q in GF(q)
159//
160//}}}
161CanonicalForm
162findGen ( int d, int q )
163{
164    Variable x( 1 );
165    CanonicalForm result;
166    cerr << "testing p = " << getCharacteristic() << ", d = " << d << " ... ";
167    cerr.flush();
168    bool ok = findGenRec( d, d, q, 0, x, result );
169    cerr << endl;
170    if ( ! ok )
171        return 0;
172    else
173        return result;
174}
175//}}}
176
177//{{{ void printTable ( int d, int q, CanonicalForm mipo )
178//{{{ docu
179//
180// printTable - print +1 table of field GF(q).
181//
182// d: degree of extension
183// q: the q in GF(q)
184// mipo: the minimal polynomial of the extension
185//
186// p: current characteristic
187//
188//}}}
189void
190printTable ( int d, int q, CanonicalForm mipo )
191{
192    int i, p = getCharacteristic();
193
194    // open file to write to
195    ostrstream fname;
196    fname << "gftables/gftable." << p << "." << d << '\0';
197    char * fn = fname.str();
198    ofstream outfile;
199    outfile.open( fn, ios::out );
200    STICKYASSERT1( outfile, "can not open GF(q) table %s for writing", fn );
201    delete fn;
202
203    cerr << "mipo = " << mipo << ": ";
204    cerr << "generating multiplicative group ... ";
205    cerr.flush();
206
207    CanonicalForm * T = new CanonicalForm[maxtable];
208    Variable x( 1 );
209
210    // fill T with powers of x
211    T[0] = 1;
212    for ( i = 1; i < q; i++ )
213        T[i] = ( T[i-1] * x ) % mipo;
214
215    cerr << "generating addition table ... ";
216    cerr.flush();
217
218    // brute force method
219    int * table = new int[maxtable];
220    CanonicalForm f;
221
222    for ( i = 0; i < q; i++ ) {
223        f = T[i] + 1;
224        int j = 0;
225        while ( j < q && T[j] != f ) j++;
226        table[i] = j;
227    }
228
229    cerr << "writing table ... ";
230    cerr.flush();
231
232    outfile << "@@ factory GF(q) table @@" << endl;
233    outfile << p << " " << d << " " << mipo << "; ";
234
235    // print simple reprenstation of mipo
236    outfile << d;
237    CFIterator MiPo = mipo;
238    for ( i = d; MiPo.hasTerms(); i--, MiPo++ ) {
239        int exp;
240        for ( exp = MiPo.exp(); exp < i; i-- )
241            outfile << " 0";
242        outfile << " " << MiPo.coeff();
243    }
244    // since mipo is irreducible, it has a constant term,
245    // so i == 0 at this point
246    outfile << endl;
247
248    int m = gf_tab_numdigits62( q );
249    char * outstr = new char[30*m+1];
250    outstr[30*m] = '\0';
251    i = 1;
252    while ( i < q ) {
253        int k = 0;
254        char * sptr = outstr;
255        while ( i < q && k < 30 ) {
256            convert62( table[i], m, sptr );
257            sptr += m;
258            k++; i++;
259        }
260        while ( k < 30 ) {
261            convert62( 0, m, sptr );
262            sptr += m;
263            k++;
264        }
265        outfile << outstr << endl;
266    }
267    outfile.close();
268
269    delete [] outstr;
270    delete [] T;
271    delete [] table;
272
273    cerr << endl;
274}
275//}}}
276
277int
278main()
279{
280    int i, p, q, n;
281    for ( i = 0; i < primes_len; i++ ) {
282        p = primes[i];
283        q = p*p;
284        n = 2;
285        setCharacteristic( p );
286        while ( q < maxtable ) {
287            CanonicalForm f = findGen( n, q );
288            ASSERT( f != 0, "no generator found" );
289            printTable( n, q, f );
290            n++; q *= p;
291        }
292    }
293}
Note: See TracBrowser for help on using the repository browser.