source: git/factory/gengftables.cc @ 8d2c11

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