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