source: git/factory/gengftables.cc @ 806c18

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