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