1 //==============================================================================================
2 //
3 //      This file is part of LiDIA --- a library for computational number theory
4 //
5 //      Copyright (c) 1994--2001 the LiDIA Group.  All rights reserved.
6 //
7 //      See http://www.informatik.tu-darmstadt.de/TI/LiDIA/
8 //
9 //----------------------------------------------------------------------------------------------
10 //
11 //      $Id$
12 //
13 //      Author  : Thomas Pfahler (TPf)
14 //      Changes : See CVS log
15 //
16 //==============================================================================================
17 
18 
19 #include <memory>
20 
21 
22 #ifdef HAVE_CONFIG_H
23 # include       "config.h"
24 #endif
25 #include        "LiDIA/galois_field.h"
26 #include        "LiDIA/finite_fields/galois_field_rep.h"
27 #include        "LiDIA/gf_element.h"
28 
29 
30 
31 #ifdef LIDIA_NAMESPACE
32 namespace LiDIA {
33 #endif
34 
35 
36 
37 //***********************************************************************
38 //*                     class galois_field_rep                          *
39 //***********************************************************************
40 
41 
42   namespace { // anonymous
43 
44     inline
45     gf_flags::gf_rep_enum
set_flag(const bigint & p,int deg)46     set_flag(const bigint &p, int deg) {
47       gf_flags::gf_rep_enum gf_rep;
48       if (deg == 1)
49         gf_rep = gf_flags::GFp;
50       else if (deg > 1) {
51         if (p == 2)
52           gf_rep = gf_flags::GF2n;
53         else
54           gf_rep = gf_flags::GFpn;
55       }
56       else gf_rep = gf_flags::UNKNOWN;
57 
58       return gf_rep;
59     }
60 
61 
62     void
update_factorization(rational_factorization & a,const rational_factorization & b)63     update_factorization(rational_factorization &a,
64                          const rational_factorization &b) {
65       // refine factorization in a using factors in b
66       for(int i = 0; i < b.no_of_comp(); i++)
67         a.refine(b.base(i));
68     }
69 
70   } // anonymous namespace
71 
72 
73   galois_field_rep *galois_field_rep::head = 0;
74 
75 
76   galois_field_rep::
galois_field_rep(const bigint & characteristic,unsigned int degree,const Fp_polynomial & pol,const rational_factorization & fact)77   galois_field_rep(const bigint& characteristic,
78                    unsigned int degree,
79                    const Fp_polynomial& pol,
80                    const rational_factorization& fact)
81     : gf_flags(),
82       I2(),
83       poly_mod(),
84       p(characteristic),
85       n(degree),
86       p_pow_n(),
87       p_pow_n_minus_1(),
88       gen(0),
89       next(0) {
90     // don't initialize the member function pointers, they are all
91     // set in this->init_functions() below
92 
93     power(this->p_pow_n, characteristic, degree);
94 
95     this->gf_rep = set_flag(characteristic, degree);
96     this->init_functions();
97     if (!characteristic.is_zero()) {
98       this->init_pol(pol);
99       this->init_fact(fact);
100     }
101   }
102 
103 
~galois_field_rep()104   galois_field_rep::~galois_field_rep()
105   {
106     if(this->gen) {
107       // not strictly necessary because `delete 0' is legal. But
108       // let's be cautious...
109       delete gen;
110       gen = 0;
111     }
112 
113     if (this == galois_field_rep::head)
114       galois_field_rep::head = next;
115     else {
116       galois_field_rep *K = galois_field_rep::head;
117       while (K->next != this) {
118         if (K->next == 0)
119           lidia_error_handler("galois_field_rep",
120                               "~galois_field_rep()::internal error");
121         K = K->next;
122       }
123       K->next = next;
124     }
125   }
126 
127 
128 
search(galois_field_rep * h,const bigint & p,unsigned int deg)129   galois_field_rep* galois_field_rep::search(galois_field_rep* h,
130                                              const bigint &p, unsigned int deg)
131     // search for field with p^deg elements in list starting with h
132     // return 0 if no such field could be found
133   {
134     while (h != 0) {
135       if (h->degree() == deg && h->characteristic() == p)
136         return h;
137       h = h->next;
138     }
139     return NULL;
140   }
141 
142 
143 
144 //
145 // static "constructors" for galois_field_rep
146 // (so we can keep a list of galois_field_rep)
147 //
148   galois_field_rep*
create(const bigint & characteristic,unsigned int degree,const rational_factorization & fact)149   galois_field_rep::create(const bigint & characteristic, unsigned int degree,
150                            const rational_factorization & fact) {
151     galois_field_rep* K = search(head, characteristic, degree);
152     if (K != 0)     // i.e. we have found a field with characteristic^degree elts.
153     {
154       update_factorization(K->p_pow_n_minus_1, fact);
155       K->rc.inc_ref_counter(); // increase ref. counter
156     }
157     else {
158       // need new galois_field_rep
159       K = new galois_field_rep(characteristic, degree, Fp_polynomial(), fact);
160       K->next = galois_field_rep::head;
161       galois_field_rep::head = K; // insert into list of fields
162     }
163     return K;
164   }
165 
166   galois_field_rep*
create(const Fp_polynomial & pol,const rational_factorization & fact)167   galois_field_rep::create(const Fp_polynomial &pol,
168                            const rational_factorization &fact)
169   {
170     debug_handler("galois_field_rep", "create(Fp_polynomial&, ...)");
171 
172     bigint p = pol.modulus();
173     int deg = pol.degree();
174     if (deg < 1 || p.is_zero())
175       lidia_error_handler("galois_field_rep",
176                           "create(Fp_polynomial, ...): bad polynomial");
177 
178     galois_field_rep* K = search(head, p, deg);
179     while (K != 0) {
180       // so far, we have found a field with p^deg elements, but we don't
181       // know whether it has the right irred. polynomial
182       if (K->irred_polynomial() == pol) {
183         // yeah, we found the field in our list
184         update_factorization(K->p_pow_n_minus_1, fact);
185         K->rc.inc_ref_counter(); // increase ref. counter
186         //output();
187         return K;
188       }
189       K = search(K->next, p, deg);
190     }
191 
192     // need new galois_field_rep
193     K = new galois_field_rep(p, deg, pol, fact);
194     K->next = galois_field_rep::head;
195     galois_field_rep::head = K; // insert into list of fields
196 
197     return K;
198   }
199 
200 
201 
init_p_pow_n_minus_1() const202   void galois_field_rep::init_p_pow_n_minus_1() const
203   {
204     debug_handler("galois_field_rep", "init_p_pow_n_minus_1()");
205 
206     rational_factorization &F = p_pow_n_minus_1;
207 
208     if (!(F.is_prime_factorization())) {
209       // p-1 divides p^n-1 for n>1
210       if (n > 1 && p != 2)  F.refine(p-1);
211 
212       F.factor_completely();
213       if (!(F.is_prime_factorization()))
214         lidia_error_handler("galois_field_rep",
215                             "init_p_pow_n_minus_1: factorization failed");
216     }
217   }
218 
219 
220 
221   const rational_factorization&
factorization_of_mult_order() const222   galois_field_rep::factorization_of_mult_order() const
223   {
224     init_p_pow_n_minus_1();
225     return p_pow_n_minus_1;
226   }
227 
228 
229 
init_functions()230   void galois_field_rep::init_functions()
231   {
232     switch(gf_rep) {
233       case GF2n:      construct = &galois_field_rep::construct_GF2n;
234         destruct = &galois_field_rep::destruct_GF2n;
235         copy = &galois_field_rep::copy_GF2n;
236         as0 = &galois_field_rep::as0_GF2n;
237         as1 = &galois_field_rep::as1_GF2n;
238         iseq = &galois_field_rep::iseq_GF2n;
239         is0 = &galois_field_rep::is0_GF2n;
240         is1 = &galois_field_rep::is1_GF2n;
241         neg = &galois_field_rep::neg_GF2n;
242         add = &galois_field_rep::add_GF2n;
243         sub = &galois_field_rep::sub_GF2n;
244         mul = &galois_field_rep::mul_GF2n;
245         inv = &galois_field_rep::inv_GF2n;
246         sqr = &galois_field_rep::sqr_GF2n;
247         hash = &galois_field_rep::hash_GF2n;
248         get_pol_rep = &galois_field_rep::get_pol_rep_GF2n;
249         set_pol_rep = &galois_field_rep::set_pol_rep_GF2n;
250         break;
251       case GFpn:      construct = &galois_field_rep::construct_GFpn;
252         destruct = &galois_field_rep::destruct_GFpn;
253         copy = &galois_field_rep::copy_GFpn;
254         as0 = &galois_field_rep::as0_GFpn;
255         as1 = &galois_field_rep::as1_GFpn;
256         iseq = &galois_field_rep::iseq_GFpn;
257         is0 = &galois_field_rep::is0_GFpn;
258         is1 = &galois_field_rep::is1_GFpn;
259         neg = &galois_field_rep::neg_GFpn;
260         add = &galois_field_rep::add_GFpn;
261         sub = &galois_field_rep::sub_GFpn;
262         mul = &galois_field_rep::mul_GFpn;
263         inv = &galois_field_rep::inv_GFpn;
264         sqr = &galois_field_rep::sqr_GFpn;
265         hash = &galois_field_rep::hash_GFpn;
266         get_pol_rep = &galois_field_rep::get_pol_rep_GFpn;
267         set_pol_rep = &galois_field_rep::set_pol_rep_GFpn;
268         break;
269       case UNKNOWN:
270       case GFp:       construct = &galois_field_rep::construct_GFp;
271         destruct = &galois_field_rep::destruct_GFp;
272         copy = &galois_field_rep::copy_GFp;
273         as0 = &galois_field_rep::as0_GFp;
274         as1 = &galois_field_rep::as1_GFp;
275         iseq = &galois_field_rep::iseq_GFp;
276         is0 = &galois_field_rep::is0_GFp;
277         is1 = &galois_field_rep::is1_GFp;
278         neg = &galois_field_rep::neg_GFp;
279         add = &galois_field_rep::add_GFp;
280         sub = &galois_field_rep::sub_GFp;
281         mul = &galois_field_rep::mul_GFp;
282         inv = &galois_field_rep::inv_GFp;
283         sqr = &galois_field_rep::sqr_GFp;
284         hash = &galois_field_rep::hash_GFp;
285         get_pol_rep = &galois_field_rep::get_pol_rep_GFp;
286         set_pol_rep = &galois_field_rep::set_pol_rep_GFp;
287         break;
288       default:        lidia_error_handler("galois_field_rep",
289                                           "init_functions: type not supported");
290     }
291   }
292 
293 
294 
init_pol(const Fp_polynomial & pol)295   void galois_field_rep::init_pol(const Fp_polynomial& pol)
296   {
297     Fp_polynomial tmp;
298     char *s, *s2;
299     int i;
300     switch (gf_rep) {
301       case GF2n:      if (pol.degree() < 0)
302         I2.init(n);
303       else {
304         s = new char[n*10];
305         s2 = new char[16];
306         sprintf(s, "%d", n); // lead coeff
307         for (i = n-1; i >= 0; i--)
308           if (!pol[i].is_zero()) {
309             sprintf(s2, " %d", i);
310             strcat(s, s2);
311           }
312         I2.init(s, n);
313         delete[] s;
314         delete[] s2;
315       }
316         break;
317       case GFpn:      if (pol.degree() < 0) {
318         build_irred(tmp, p, n);
319         poly_mod.build(tmp);
320       }
321       else
322         poly_mod.build(pol);
323         break;
324       case GFp:       if (pol.degree() < 0) {
325         tmp.assign_x(p);
326         poly_mod.build(tmp);
327       }
328       else
329         poly_mod.build(pol);
330         break;
331       default:        lidia_error_handler("galois_field_rep",
332                                           "init_pol: type UNKNOWN not supported");
333     }
334   }
335 
336 
337 
init_fact(const rational_factorization & fact)338   void galois_field_rep::init_fact(const rational_factorization &fact)
339   {
340     if (fact.no_of_comp() == 0)//1 && fact.base(0).is_one() && fact.sign() == 1)
341     {
342       // no factorization was provided
343       if (p == 2 && n > 30 && !(n & 1)) {
344         bigint q;
345         unsigned int i = n;
346         while (!(i & 1) && i > 20)
347           i >>= 1;
348         shift_left(q, bigint(1), i);
349         multiply(p_pow_n_minus_1, q-bigint(1), q+bigint(1));
350         i <<= 1;
351         while (i < n) {
352           square(q, q);
353           multiply(p_pow_n_minus_1, p_pow_n_minus_1, q+bigint(1));
354           i <<= 1;
355         }
356       }
357       else
358         p_pow_n_minus_1.assign(p_pow_n - 1);
359     }
360     else {
361       bigrational tmp = evaluate(fact);
362       if (tmp+1 != p_pow_n)
363         lidia_error_handler("galois_field_rep",
364                             "galois_field_rep: bad factorization");
365       p_pow_n_minus_1.assign(fact);
366     }
367   }
368 
369 
370 
irred_polynomial() const371   Fp_polynomial galois_field_rep::irred_polynomial() const
372   {
373     Fp_polynomial pol;
374     int i;
375     switch (gf_rep) {
376       case GFp:
377       case GFpn:
378         return poly_mod.modulus();
379       case GF2n:
380         pol.set_modulus(2);
381         pol.set_coefficient(n);
382         pol.set_coefficient(0);
383         if (I2.invert_p == &info_gf2n::tri_invert)
384           pol.set_coefficient(I2.exp1);
385         else if (I2.invert_p == &info_gf2n::pent_invert) {
386           pol.set_coefficient(I2.exp1);
387           pol.set_coefficient(I2.exp2);
388           pol.set_coefficient(I2.exp3);
389         }
390         else if (I2.invert_p == &info_gf2n::general_invert) {
391           for (i = I2.anz_exponents-1; i >= 0; i--)
392             pol.set_coefficient(I2.exponents[i]);
393         }
394         else
395           lidia_error_handler("galois_field_rep",
396                               "irred_polynomial(): internal error");
397         break;
398       default:
399         lidia_error_handler("galois_field_rep",
400                             "irred_polynomial(): no field specified");
401     }
402     return pol;
403   }
404 
405 
406   gf_element const&
generator() const407   galois_field_rep::generator() const {
408     if(!this->gen) {
409       std::auto_ptr<gf_element> new_gen (new gf_element());
410       new_gen->assign_primitive_element(galois_field(*this));
411       this->gen = new_gen.release();
412     }
413 
414     return *this->gen;
415   }
416 
417 
418 #ifdef LIDIA_NAMESPACE
419 }       // end of namespace LiDIA
420 #endif
421