source: git/factory/gengftables.cc @ c44985

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