![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to fff CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [local] / OpenXM_contrib2 / asir2000 / lib|
Return to fff CVS log | Up to [local] / OpenXM_contrib2 / asir2000 / lib |
1.1 ! noro 1: /* $OpenXM: OpenXM/src/asir99/lib/fff,v 1.1.1.1 1999/11/10 08:12:31 noro Exp $ */
! 2: /*
! 3: fff : Univariate factorizer over a finite field.
! 4:
! 5: Revision History:
! 6:
! 7: 99/05/18 noro the first official version
! 8: 99/06/11 noro
! 9: 99/07/27 noro
! 10: */
! 11:
! 12: #include "defs.h"
! 13:
! 14: extern TPMOD,TQMOD$
! 15:
! 16: /*
! 17: Input : a univariate polynomial F
! 18: Output: a list [[F1,M1],[F2,M2],...], where
! 19: Fi is a monic irreducible factor, Mi is its multiplicity.
! 20: The leading coefficient of F is abondoned.
! 21: */
! 22:
! 23: def fctr_ff(F)
! 24: {
! 25: F = simp_ff(F);
! 26: F = F/LCOEF(F);
! 27: L = sqfr_ff(F);
! 28: for ( R = [], T = L; T != []; T = cdr(T) ) {
! 29: S = car(T); A = S[0]; E = S[1];
! 30: B = ddd_ff(A);
! 31: R = append(append_mult_ff(B,E),R);
! 32: }
! 33: return R;
! 34: }
! 35:
! 36: /*
! 37: Input : a list of polynomial L; an integer E
! 38: Output: a list s.t. [[L0,E],[L1,E],...]
! 39: where Li = L[i]/leading coef of L[i]
! 40: */
! 41:
! 42: def append_mult_ff(L,E)
! 43: {
! 44: for ( T = L, R = []; T != []; T = cdr(T) )
! 45: R = cons([car(T)/LCOEF(car(T)),E],R);
! 46: return R;
! 47: }
! 48:
! 49: /*
! 50: Input : a polynomial F
! 51: Output: a list [[F1,M1],[F2,M2],...]
! 52: where Fi is a square free factor,
! 53: Mi is its multiplicity.
! 54: */
! 55:
! 56: def sqfr_ff(F)
! 57: {
! 58: V = var(F);
! 59: F1 = diff(F,V);
! 60: L = [];
! 61: /* F=H*Fq^p => F'=H'*Fq^p => gcd(F,F')=gcd(H,H')*Fq^p */
! 62: if ( F1 != 0 ) {
! 63: F1 = F1/LCOEF(F1);
! 64: F2 = ugcd(F,F1);
! 65: /* FLAT = H/gcd(H,H') : square free part of H */
! 66: FLAT = sdiv(F,F2);
! 67: I = 0;
! 68: /* square free factorization of H */
! 69: while ( deg(FLAT,V) ) {
! 70: while ( 1 ) {
! 71: QR = sqr(F,FLAT);
! 72: if ( !QR[1] ) {
! 73: F = QR[0]; I++;
! 74: } else
! 75: break;
! 76: }
! 77: if ( !deg(F,V) )
! 78: FLAT1 = simp_ff(1);
! 79: else
! 80: FLAT1 = ugcd(F,FLAT);
! 81: G = sdiv(FLAT,FLAT1);
! 82: FLAT = FLAT1;
! 83: L = cons([G,I],L);
! 84: }
! 85: }
! 86: /* now F = Fq^p */
! 87: if ( deg(F,V) ) {
! 88: Char = characteristic_ff();
! 89: T = sqfr_ff(pthroot_p_ff(F));
! 90: for ( R = []; T != []; T = cdr(T) ) {
! 91: H = car(T); R = cons([H[0],Char*H[1]],R);
! 92: }
! 93: } else
! 94: R = [];
! 95: return append(L,R);
! 96: }
! 97:
! 98: /*
! 99: Input : a polynomial F
! 100: Output: F^(1/char)
! 101: */
! 102:
! 103: def pthroot_p_ff(F)
! 104: {
! 105: V = var(F);
! 106: DVR = characteristic_ff();
! 107: PWR = DVR^(extdeg_ff()-1);
! 108: for ( T = F, R = 0; T; ) {
! 109: D1 = deg(T,V); C = coef(T,D1,V); T -= C*V^D1;
! 110: R += C^PWR*V^idiv(D1,DVR);
! 111: }
! 112: return R;
! 113: }
! 114:
! 115: /*
! 116: Input : a polynomial F of degree N
! 117: Output: a list [V^Ord mod F,Tab]
! 118: where V = var(F), Ord = field order
! 119: Tab[i] = V^(i*Ord) mod F (i=0,...,N-1)
! 120: */
! 121:
! 122: def tab_ff(F)
! 123: {
! 124: V = var(F);
! 125: N = deg(F,V);
! 126: F = F/LCOEF(F);
! 127: XP = pwrmod_ff(F);
! 128: R = pwrtab_ff(F,XP);
! 129: return R;
! 130: }
! 131:
! 132: /*
! 133: Input : a square free polynomial F
! 134: Output: a list [F1,F2,...]
! 135: where Fi is an irreducible factor of F.
! 136: */
! 137:
! 138: def ddd_ff(F)
! 139: {
! 140: V = var(F);
! 141: if ( deg(F,V) == 1 )
! 142: return [F];
! 143: TAB = tab_ff(F);
! 144: for ( I = 1, W = V, L = []; 2*I <= deg(F,V); I++ ) {
! 145: lazy_lm(1);
! 146: for ( T = 0, K = 0; K <= deg(W,V); K++ )
! 147: if ( C = coef(W,K,V) )
! 148: T += TAB[K]*C;
! 149: lazy_lm(0);
! 150: W = simp_ff(T);
! 151: GCD = ugcd(F,W-V);
! 152: if ( deg(GCD,V) ) {
! 153: L = append(berlekamp_ff(GCD,I,TAB),L);
! 154: F = sdiv(F,GCD);
! 155: W = urem(W,F);
! 156: }
! 157: }
! 158: if ( deg(F,V) )
! 159: return cons(F,L);
! 160: else
! 161: return L;
! 162: }
! 163:
! 164: /*
! 165: Input : a polynomial
! 166: Output: 1 if F is irreducible
! 167: 0 otherwise
! 168: */
! 169:
! 170: def irredcheck_ff(F)
! 171: {
! 172: V = var(F);
! 173: if ( deg(F,V) <= 1 )
! 174: return 1;
! 175: F1 = diff(F,V);
! 176: if ( !F1 )
! 177: return 0;
! 178: F1 = F1/LCOEF(F1);
! 179: if ( deg(ugcd(F,F1),V) > 0 )
! 180: return 0;
! 181: TAB = tab_ff(F);
! 182: for ( I = 1, W = V, L = []; 2*I <= deg(F,V); I++ ) {
! 183: for ( T = 0, K = 0; K <= deg(W,V); K++ )
! 184: if ( C = coef(W,K,V) )
! 185: T += TAB[K]*C;
! 186: W = T;
! 187: GCD = ugcd(F,W-V);
! 188: if ( deg(GCD,V) )
! 189: return 0;
! 190: }
! 191: return 1;
! 192: }
! 193:
! 194: /*
! 195: Input : a square free (canonical) modular polynomial F
! 196: Output: a list of polynomials [LF,CF,XP] where
! 197: LF=the product of all the linear factors
! 198: CF=F/LF
! 199: XP=x^field_order mod CF
! 200: */
! 201:
! 202: def meq_linear_part_ff(F)
! 203: {
! 204: F = simp_ff(F);
! 205: F = F/LCOEF(F);
! 206: V = var(F);
! 207: if ( deg(F,V) == 1 )
! 208: return [F,1,0];
! 209: T0 = time()[0];
! 210: XP = pwrmod_ff(F);
! 211: GCD = ugcd(F,XP-V);
! 212: if ( deg(GCD,V) ) {
! 213: GCD = GCD/LCOEF(GCD);
! 214: F = sdiv(F,GCD);
! 215: XP = srem(XP,F);
! 216: R = GCD;
! 217: } else
! 218: R = 1;
! 219: TPMOD += time()[0]-T0;
! 220: return [R,F,XP];
! 221: }
! 222:
! 223: /*
! 224: Input : a square free polynomial F s.t.
! 225: all the irreducible factors of F
! 226: has the same degree D.
! 227: Output: D
! 228: */
! 229:
! 230: def meq_ed_ff(F,XP)
! 231: {
! 232: T0 = time()[0];
! 233: F = simp_ff(F);
! 234: F = F/LCOEF(F);
! 235: V = var(F);
! 236:
! 237: TAB = pwrtab_ff(F,XP);
! 238:
! 239: D = deg(F,V);
! 240: for ( I = 1, W = V, L = []; 2*I <= D; I++ ) {
! 241: lazy_lm(1);
! 242: for ( T = 0, K = 0; K <= deg(W,V); K++ )
! 243: if ( C = coef(W,K,V) )
! 244: T += TAB[K]*C;
! 245: lazy_lm(0);
! 246: W = simp_ff(T);
! 247: if ( W == V ) {
! 248: D = I; break;
! 249: }
! 250: }
! 251: TQMOD += time()[0]-T0;
! 252: return D;
! 253: }
! 254:
! 255: /*
! 256: Input : a square free polynomial F
! 257: an integer E
! 258: an array TAB
! 259: where all the irreducible factors of F has degree E
! 260: and TAB[i] = V^(i*Ord) mod F. (V=var(F), Ord=field order)
! 261: Output: a list containing all the irreducible factors of F
! 262: */
! 263:
! 264: def berlekamp_ff(F,E,TAB)
! 265: {
! 266: V = var(F);
! 267: N = deg(F,V);
! 268: Q = newmat(N,N);
! 269: for ( J = 0; J < N; J++ ) {
! 270: T = urem(TAB[J],F);
! 271: for ( I = 0; I < N; I++ ) {
! 272: Q[I][J] = coef(T,I);
! 273: }
! 274: }
! 275: for ( I = 0; I < N; I++ )
! 276: Q[I][I] -= simp_ff(1);
! 277: L = nullspace_ff(Q); MT = L[0]; IND = L[1];
! 278: NF0 = N/E;
! 279: PS = null_to_poly_ff(MT,IND,V);
! 280: R = newvect(NF0); R[0] = F/LCOEF(F);
! 281: for ( I = 1, NF = 1; NF < NF0 && I < NF0; I++ ) {
! 282: PSI = PS[I];
! 283: MP = minipoly_ff(PSI,F);
! 284: ROOT = find_root_ff(MP); NR = length(ROOT);
! 285: for ( J = 0; J < NF; J++ ) {
! 286: if ( deg(R[J],V) == E )
! 287: continue;
! 288: for ( K = 0; K < NR; K++ ) {
! 289: GCD = ugcd(R[J],PSI-ROOT[K]);
! 290: if ( deg(GCD,V) > 0 && deg(GCD,V) < deg(R[J],V) ) {
! 291: Q = sdiv(R[J],GCD);
! 292: R[J] = Q; R[NF++] = GCD;
! 293: }
! 294: }
! 295: }
! 296: }
! 297: return vtol(R);
! 298: }
! 299:
! 300: /*
! 301: Input : a matrix MT
! 302: an array IND
! 303: an indeterminate V
! 304: MT is a matrix after Gaussian elimination
! 305: IND[I] = 0 means that i-th column of MT represents a basis
! 306: element of the null space.
! 307: Output: an array R which contains all the basis element of
! 308: the null space of MT. Here, a basis element E is represented
! 309: as a polynomial P of V s.t. coef(P,i) = E[i].
! 310: */
! 311:
! 312: def null_to_poly_ff(MT,IND,V)
! 313: {
! 314: N = size(MT)[0];
! 315: for ( I = 0, J = 0; I < N; I++ )
! 316: if ( IND[I] )
! 317: J++;
! 318: R = newvect(J);
! 319: for ( I = 0, L = 0; I < N; I++ ) {
! 320: if ( !IND[I] )
! 321: continue;
! 322: for ( J = K = 0, T = 0; J < N; J++ )
! 323: if ( !IND[J] )
! 324: T += MT[K++][I]*V^J;
! 325: else if ( J == I )
! 326: T -= V^I;
! 327: R[L++] = simp_ff(T);
! 328: }
! 329: return R;
! 330: }
! 331:
! 332: /*
! 333: Input : a polynomial P, a polynomial F
! 334: Output: a minimal polynomial MP(V) of P mod F.
! 335: */
! 336:
! 337: def minipoly_ff(P,F)
! 338: {
! 339: V = var(P);
! 340: P0 = P1 = simp_ff(1);
! 341: L = [[P0,P0]];
! 342: while ( 1 ) {
! 343: /* P0 = V^K, P1 = P^K mod F */
! 344: P0 *= V;
! 345: P1 = urem(P*P1,F);
! 346: /*
! 347: NP0 = P0-c1L1_0-c2L2_0-...,
! 348: NP1 is a normal form w.r.t. [L1_1,L2_1,...]
! 349: NP1 = P1-c1L1_1-c2L2_1-...,
! 350: NP0 represents the normal form computation.
! 351: */
! 352: L1 = lnf_ff(P0,P1,L,V); NP0 = L1[0]; NP1 = L1[1];
! 353: if ( !NP1 )
! 354: return NP0;
! 355: else
! 356: L = lnf_insert([NP0,NP1],L,V);
! 357: }
! 358: }
! 359:
! 360: /*
! 361: Input ; a list of polynomials [P0,P1] = [V^K,P^K mod F]
! 362: a sorted list L=[[L1_0,L1_1],[L2_0,L2_1],...]
! 363: of previously computed pairs of polynomials
! 364: an indeterminate V
! 365: Output: a list of polynomials [NP0,NP1]
! 366: where NP1 = P1-c1L1_1-c2L2_1-...,
! 367: NP0 = P0-c1L1_0-c2L2_0-...,
! 368: NP1 is a normal form w.r.t. [L1_1,L2_1,...]
! 369: NP0 represents the normal form computation.
! 370: [L1_1,L_2_1,...] is sorted so that it is a triangular
! 371: linear basis s.t. deg(Li_1) > deg(Lj_1) for i<j.
! 372: */
! 373:
! 374: def lnf_ff(P0,P1,L,V)
! 375: {
! 376: NP0 = P0; NP1 = P1;
! 377: for ( T = L; T != []; T = cdr(T) ) {
! 378: Q = car(T);
! 379: D1 = deg(NP1,V);
! 380: if ( D1 == deg(Q[1],V) ) {
! 381: H = -coef(NP1,D1,V)/coef(Q[1],D1,V);
! 382: NP0 += Q[0]*H;
! 383: NP1 += Q[1]*H;
! 384: }
! 385: }
! 386: return [NP0,NP1];
! 387: }
! 388:
! 389: /*
! 390: Input : a pair of polynomial P=[P0,P1],
! 391: a list L,
! 392: an indeterminate V
! 393: Output: a list L1 s.t. L1 contains P and L
! 394: and L1 is sorted in the decreasing order
! 395: w.r.t. the degree of the second element
! 396: of elements in L1.
! 397: */
! 398:
! 399: def lnf_insert(P,L,V)
! 400: {
! 401: if ( L == [] )
! 402: return [P];
! 403: else {
! 404: P0 = car(L);
! 405: if ( deg(P0[1],V) > deg(P[1],V) )
! 406: return cons(P0,lnf_insert(P,cdr(L),V));
! 407: else
! 408: return cons(P,L);
! 409: }
! 410: }
! 411:
! 412: /*
! 413: Input : a square free polynomial F s.t.
! 414: all the irreducible factors of F
! 415: has the degree E.
! 416: Output: a list containing all the irreducible factors of F
! 417: */
! 418:
! 419: def c_z_ff(F,E)
! 420: {
! 421: Type = field_type_ff();
! 422: if ( Type == 1 || Type == 3 )
! 423: return c_z_lm(F,E);
! 424: else
! 425: return c_z_gf2n(F,E);
! 426: }
! 427:
! 428: /*
! 429: Input : a square free polynomial P s.t. P splits into linear factors
! 430: Output: a list containing all the root of P
! 431: */
! 432:
! 433: def find_root_ff(P)
! 434: {
! 435: V = var(P);
! 436: L = c_z_ff(P,1);
! 437: for ( T = L, U = []; T != []; T = cdr(T) ) {
! 438: S = car(T)/LCOEF(car(T)); U = cons(-coef(S,0,V),U);
! 439: }
! 440: return U;
! 441: }
! 442:
! 443: /*
! 444: Input : a square free polynomial F s.t.
! 445: all the irreducible factors of F
! 446: has the degree E.
! 447: Output: an irreducible factor of F
! 448: */
! 449:
! 450: def c_z_one_ff(F,E)
! 451: {
! 452: Type = field_type_ff();
! 453: if ( Type == 1 || Type == 3 )
! 454: return c_z_one_lm(F,E);
! 455: else
! 456: return c_z_one_gf2n(F,E);
! 457: }
! 458:
! 459: /*
! 460: Input : a square free polynomial P s.t. P splits into linear factors
! 461: Output: a list containing a root of P
! 462: */
! 463:
! 464: def find_one_root_ff(P)
! 465: {
! 466: V = var(P);
! 467: LF = c_z_one_ff(P,1);
! 468: U = -coef(LF/LCOEF(LF),0,V);
! 469: return [U];
! 470: }
! 471:
! 472: /*
! 473: Input : an integer N; an indeterminate V
! 474: Output: a polynomial F s.t. var(F) = V, deg(F) < N
! 475: and its coefs are random numbers in
! 476: the ground field.
! 477: */
! 478:
! 479: def randpoly_ff(N,V)
! 480: {
! 481: for ( I = 0, S = 0; I < N; I++ )
! 482: S += random_ff()*V^I;
! 483: return S;
! 484: }
! 485:
! 486: /*
! 487: Input : an integer N; an indeterminate V
! 488: Output: a monic polynomial F s.t. var(F) = V, deg(F) = N-1
! 489: and its coefs are random numbers in
! 490: the ground field except for the leading term.
! 491: */
! 492:
! 493: def monic_randpoly_ff(N,V)
! 494: {
! 495: for ( I = 0, N1 = N-1, S = 0; I < N1; I++ )
! 496: S += random_ff()*V^I;
! 497: return V^N1+S;
! 498: }
! 499:
! 500: /* GF(p) specific functions */
! 501:
! 502: /*
! 503: Input : a square free polynomial F s.t.
! 504: all the irreducible factors of F
! 505: has the degree E.
! 506: Output: a list containing all the irreducible factors of F
! 507: */
! 508:
! 509: def c_z_lm(F,E)
! 510: {
! 511: V = var(F);
! 512: N = deg(F,V);
! 513: if ( N == E )
! 514: return [F];
! 515: M = field_order_ff();
! 516: K = idiv(N,E);
! 517: L = [F];
! 518: while ( 1 ) {
! 519: W = monic_randpoly_ff(2*E,V);
! 520: T = generic_pwrmod_ff(W,F,idiv(M^E-1,2));
! 521: W = T-1;
! 522: if ( !W )
! 523: continue;
! 524: G = ugcd(F,W);
! 525: if ( deg(G,V) && deg(G,V) < N ) {
! 526: L1 = c_z_lm(G,E);
! 527: L2 = c_z_lm(sdiv(F,G),E);
! 528: return append(L1,L2);
! 529: }
! 530: }
! 531: }
! 532:
! 533: /*
! 534: Input : a square free polynomial F s.t.
! 535: all the irreducible factors of F
! 536: has the degree E.
! 537: Output: an irreducible factor of F
! 538: */
! 539:
! 540: def c_z_one_lm(F,E)
! 541: {
! 542: V = var(F);
! 543: N = deg(F,V);
! 544: if ( N == E )
! 545: return F;
! 546: M = field_order_ff();
! 547: K = idiv(N,E);
! 548: while ( 1 ) {
! 549: W = monic_randpoly_ff(2*E,V);
! 550: T = generic_pwrmod_ff(W,F,idiv(M^E-1,2));
! 551: W = T-1;
! 552: if ( W ) {
! 553: G = ugcd(F,W);
! 554: D = deg(G,V);
! 555: if ( D && D < N ) {
! 556: if ( 2*D <= N ) {
! 557: F1 = G; F2 = sdiv(F,G);
! 558: } else {
! 559: F2 = G; F1 = sdiv(F,G);
! 560: }
! 561: return c_z_one_lm(F1,E);
! 562: }
! 563: }
! 564: }
! 565: }
! 566:
! 567: /* GF(2^n) specific functions */
! 568:
! 569: /*
! 570: Input : a square free polynomial F s.t.
! 571: all the irreducible factors of F
! 572: has the degree E.
! 573: Output: a list containing all the irreducible factors of F
! 574: */
! 575:
! 576: def c_z_gf2n(F,E)
! 577: {
! 578: V = var(F);
! 579: N = deg(F,V);
! 580: if ( N == E )
! 581: return [F];
! 582: K = idiv(N,E);
! 583: L = [F];
! 584: while ( 1 ) {
! 585: W = randpoly_ff(2*E,V);
! 586: T = tracemod_gf2n(W,F,E);
! 587: W = T-1;
! 588: if ( !W )
! 589: continue;
! 590: G = ugcd(F,W);
! 591: if ( deg(G,V) && deg(G,V) < N ) {
! 592: L1 = c_z_gf2n(G,E);
! 593: L2 = c_z_gf2n(sdiv(F,G),E);
! 594: return append(L1,L2);
! 595: }
! 596: }
! 597: }
! 598:
! 599: /*
! 600: Input : a square free polynomial F s.t.
! 601: all the irreducible factors of F
! 602: has the degree E.
! 603: Output: an irreducible factor of F
! 604: */
! 605:
! 606: def c_z_one_gf2n(F,E)
! 607: {
! 608: V = var(F);
! 609: N = deg(F,V);
! 610: if ( N == E )
! 611: return F;
! 612: K = idiv(N,E);
! 613: while ( 1 ) {
! 614: W = randpoly_ff(2*E,V);
! 615: T = tracemod_gf2n(W,F,E);
! 616: W = T-1;
! 617: if ( W ) {
! 618: G = ugcd(F,W);
! 619: D = deg(G,V);
! 620: if ( D && D < N ) {
! 621: if ( 2*D <= N ) {
! 622: F1 = G; F2 = sdiv(F,G);
! 623: } else {
! 624: F2 = G; F1 = sdiv(F,G);
! 625: }
! 626: return c_z_one_gf2n(F1,E);
! 627: }
! 628: }
! 629: }
! 630: }
! 631:
! 632: /*
! 633: Input : an integer D
! 634: Output: an irreducible polynomial F over GF(2)
! 635: of degree D.
! 636: */
! 637:
! 638: def defpoly_mod2(D)
! 639: {
! 640: return gf2ntop(irredpoly_up2(D,0));
! 641: }
! 642:
! 643: def dummy_time() {
! 644: return [0,0,0,0];
! 645: }
! 646: end$