Annotation of OpenXM_contrib2/asir2018/lib/fff, Revision 1.1
1.1 ! noro 1: /*
! 2: * Copyright (c) 1994-2000 FUJITSU LABORATORIES LIMITED
! 3: * All rights reserved.
! 4: *
! 5: * FUJITSU LABORATORIES LIMITED ("FLL") hereby grants you a limited,
! 6: * non-exclusive and royalty-free license to use, copy, modify and
! 7: * redistribute, solely for non-commercial and non-profit purposes, the
! 8: * computer program, "Risa/Asir" ("SOFTWARE"), subject to the terms and
! 9: * conditions of this Agreement. For the avoidance of doubt, you acquire
! 10: * only a limited right to use the SOFTWARE hereunder, and FLL or any
! 11: * third party developer retains all rights, including but not limited to
! 12: * copyrights, in and to the SOFTWARE.
! 13: *
! 14: * (1) FLL does not grant you a license in any way for commercial
! 15: * purposes. You may use the SOFTWARE only for non-commercial and
! 16: * non-profit purposes only, such as academic, research and internal
! 17: * business use.
! 18: * (2) The SOFTWARE is protected by the Copyright Law of Japan and
! 19: * international copyright treaties. If you make copies of the SOFTWARE,
! 20: * with or without modification, as permitted hereunder, you shall affix
! 21: * to all such copies of the SOFTWARE the above copyright notice.
! 22: * (3) An explicit reference to this SOFTWARE and its copyright owner
! 23: * shall be made on your publication or presentation in any form of the
! 24: * results obtained by use of the SOFTWARE.
! 25: * (4) In the event that you modify the SOFTWARE, you shall notify FLL by
! 26: * e-mail at risa-admin@sec.flab.fujitsu.co.jp of the detailed specification
! 27: * for such modification or the source code of the modified part of the
! 28: * SOFTWARE.
! 29: *
! 30: * THE SOFTWARE IS PROVIDED AS IS WITHOUT ANY WARRANTY OF ANY KIND. FLL
! 31: * MAKES ABSOLUTELY NO WARRANTIES, EXPRESSED, IMPLIED OR STATUTORY, AND
! 32: * EXPRESSLY DISCLAIMS ANY IMPLIED WARRANTY OF MERCHANTABILITY, FITNESS
! 33: * FOR A PARTICULAR PURPOSE OR NONINFRINGEMENT OF THIRD PARTIES'
! 34: * RIGHTS. NO FLL DEALER, AGENT, EMPLOYEES IS AUTHORIZED TO MAKE ANY
! 35: * MODIFICATIONS, EXTENSIONS, OR ADDITIONS TO THIS WARRANTY.
! 36: * UNDER NO CIRCUMSTANCES AND UNDER NO LEGAL THEORY, TORT, CONTRACT,
! 37: * OR OTHERWISE, SHALL FLL BE LIABLE TO YOU OR ANY OTHER PERSON FOR ANY
! 38: * DIRECT, INDIRECT, SPECIAL, INCIDENTAL, PUNITIVE OR CONSEQUENTIAL
! 39: * DAMAGES OF ANY CHARACTER, INCLUDING, WITHOUT LIMITATION, DAMAGES
! 40: * ARISING OUT OF OR RELATING TO THE SOFTWARE OR THIS AGREEMENT, DAMAGES
! 41: * FOR LOSS OF GOODWILL, WORK STOPPAGE, OR LOSS OF DATA, OR FOR ANY
! 42: * DAMAGES, EVEN IF FLL SHALL HAVE BEEN INFORMED OF THE POSSIBILITY OF
! 43: * SUCH DAMAGES, OR FOR ANY CLAIM BY ANY OTHER PARTY. EVEN IF A PART
! 44: * OF THE SOFTWARE HAS BEEN DEVELOPED BY A THIRD PARTY, THE THIRD PARTY
! 45: * DEVELOPER SHALL HAVE NO LIABILITY IN CONNECTION WITH THE USE,
! 46: * PERFORMANCE OR NON-PERFORMANCE OF THE SOFTWARE.
! 47: *
! 48: * $OpenXM$
! 49: */
! 50: /*
! 51: fff : Univariate factorizer over a finite field.
! 52:
! 53: Revision History:
! 54:
! 55: 99/05/18 noro the first official version
! 56: 99/06/11 noro
! 57: 99/07/27 noro
! 58: */
! 59: module fff $
! 60: /* Empty for now. It will be used in a future. */
! 61: endmodule $
! 62:
! 63: #include "defs.h"
! 64:
! 65: extern TPMOD,TQMOD$
! 66:
! 67: /*
! 68: Input : a univariate polynomial F
! 69: Output: a list [[F1,M1],[F2,M2],...], where
! 70: Fi is a monic irreducible factor, Mi is its multiplicity.
! 71: The leading coefficient of F is abondoned.
! 72: */
! 73:
! 74: def fctr_ff(F)
! 75: {
! 76: F = simp_ff(F);
! 77: F = F/LCOEF(F);
! 78: L = sqfr_ff(F);
! 79: for ( R = [], T = L; T != []; T = cdr(T) ) {
! 80: S = car(T); A = S[0]; E = S[1];
! 81: B = ddd_ff(A);
! 82: R = append(append_mult_ff(B,E),R);
! 83: }
! 84: return R;
! 85: }
! 86:
! 87: /*
! 88: Input : a list of polynomial L; an integer E
! 89: Output: a list s.t. [[L0,E],[L1,E],...]
! 90: where Li = L[i]/leading coef of L[i]
! 91: */
! 92:
! 93: def append_mult_ff(L,E)
! 94: {
! 95: for ( T = L, R = []; T != []; T = cdr(T) )
! 96: R = cons([car(T)/LCOEF(car(T)),E],R);
! 97: return R;
! 98: }
! 99:
! 100: /*
! 101: Input : a polynomial F
! 102: Output: a list [[F1,M1],[F2,M2],...]
! 103: where Fi is a square free factor,
! 104: Mi is its multiplicity.
! 105: */
! 106:
! 107: def sqfr_ff(F)
! 108: {
! 109: V = var(F);
! 110: F1 = diff(F,V);
! 111: L = [];
! 112: /* F=H*Fq^p => F'=H'*Fq^p => gcd(F,F')=gcd(H,H')*Fq^p */
! 113: if ( F1 != 0 ) {
! 114: F1 = F1/LCOEF(F1);
! 115: F2 = ugcd(F,F1);
! 116: /* FLAT = H/gcd(H,H') : square free part of H */
! 117: FLAT = sdiv(F,F2);
! 118: FLAT /= LCOEF(FLAT);
! 119: I = 0;
! 120: /* square free factorization of H */
! 121: while ( deg(FLAT,V) ) {
! 122: while ( 1 ) {
! 123: QR = sqr(F,FLAT);
! 124: if ( !QR[1] ) {
! 125: F = QR[0]; I++;
! 126: } else
! 127: break;
! 128: }
! 129: if ( !deg(F,V) )
! 130: FLAT1 = simp_ff(1);
! 131: else
! 132: FLAT1 = ugcd(F,FLAT);
! 133: FLAT1 /= LCOEF(FLAT1);
! 134: G = sdiv(FLAT,FLAT1);
! 135: FLAT = FLAT1;
! 136: L = cons([G,I],L);
! 137: }
! 138: }
! 139: /* now F = Fq^p */
! 140: if ( deg(F,V) ) {
! 141: Char = characteristic_ff();
! 142: T = sqfr_ff(pthroot_p_ff(F));
! 143: for ( R = []; T != []; T = cdr(T) ) {
! 144: H = car(T); R = cons([H[0],Char*H[1]],R);
! 145: }
! 146: } else
! 147: R = [];
! 148: return append(L,R);
! 149: }
! 150:
! 151: /*
! 152: Input : a polynomial F
! 153: Output: F^(1/char)
! 154: */
! 155:
! 156: def pthroot_p_ff(F)
! 157: {
! 158: V = var(F);
! 159: DVR = characteristic_ff();
! 160: PWR = DVR^(extdeg_ff()-1);
! 161: for ( T = F, R = 0; T; ) {
! 162: D1 = deg(T,V); C = coef(T,D1,V); T -= C*V^D1;
! 163: R += C^PWR*V^idiv(D1,DVR);
! 164: }
! 165: return R;
! 166: }
! 167:
! 168: /*
! 169: Input : a polynomial F of degree N
! 170: Output: a list [V^Ord mod F,Tab]
! 171: where V = var(F), Ord = field order
! 172: Tab[i] = V^(i*Ord) mod F (i=0,...,N-1)
! 173: */
! 174:
! 175: def tab_ff(F)
! 176: {
! 177: V = var(F);
! 178: N = deg(F,V);
! 179: F = F/LCOEF(F);
! 180: XP = pwrmod_ff(F);
! 181: R = pwrtab_ff(F,XP);
! 182: return R;
! 183: }
! 184:
! 185: /*
! 186: Input : a square free polynomial F
! 187: Output: a list [F1,F2,...]
! 188: where Fi is an irreducible factor of F.
! 189: */
! 190:
! 191: def ddd_ff(F)
! 192: {
! 193: V = var(F);
! 194: if ( deg(F,V) == 1 )
! 195: return [F];
! 196: TAB = tab_ff(F);
! 197: for ( I = 1, W = V, L = []; 2*I <= deg(F,V); I++ ) {
! 198: lazy_lm(1);
! 199: for ( T = 0, K = 0; K <= deg(W,V); K++ )
! 200: if ( C = coef(W,K,V) )
! 201: T += TAB[K]*C;
! 202: lazy_lm(0);
! 203: W = simp_ff(T);
! 204: GCD = ugcd(F,W-V);
! 205: if ( deg(GCD,V) ) {
! 206: L = append(berlekamp_ff(GCD,I,TAB),L);
! 207: F = sdiv(F,GCD);
! 208: W = urem(W,F);
! 209: }
! 210: }
! 211: if ( deg(F,V) )
! 212: return cons(F,L);
! 213: else
! 214: return L;
! 215: }
! 216:
! 217: /*
! 218: Input : a polynomial
! 219: Output: 1 if F is irreducible
! 220: 0 otherwise
! 221: */
! 222:
! 223: def irredcheck_ff(F)
! 224: {
! 225: V = var(F);
! 226: if ( deg(F,V) <= 1 )
! 227: return 1;
! 228: F1 = diff(F,V);
! 229: if ( !F1 )
! 230: return 0;
! 231: F1 = F1/LCOEF(F1);
! 232: if ( deg(ugcd(F,F1),V) > 0 )
! 233: return 0;
! 234: TAB = tab_ff(F);
! 235: for ( I = 1, W = V, L = []; 2*I <= deg(F,V); I++ ) {
! 236: for ( T = 0, K = 0; K <= deg(W,V); K++ )
! 237: if ( C = coef(W,K,V) )
! 238: T += TAB[K]*C;
! 239: W = T;
! 240: GCD = ugcd(F,W-V);
! 241: if ( deg(GCD,V) )
! 242: return 0;
! 243: }
! 244: return 1;
! 245: }
! 246:
! 247: /*
! 248: Input : a square free (canonical) modular polynomial F
! 249: Output: a list of polynomials [LF,CF,XP] where
! 250: LF=the product of all the linear factors
! 251: CF=F/LF
! 252: XP=x^field_order mod CF
! 253: */
! 254:
! 255: def meq_linear_part_ff(F)
! 256: {
! 257: F = simp_ff(F);
! 258: F = F/LCOEF(F);
! 259: V = var(F);
! 260: if ( deg(F,V) == 1 )
! 261: return [F,1,0];
! 262: T0 = time()[0];
! 263: XP = pwrmod_ff(F);
! 264: GCD = ugcd(F,XP-V);
! 265: if ( deg(GCD,V) ) {
! 266: GCD = GCD/LCOEF(GCD);
! 267: F = sdiv(F,GCD);
! 268: XP = srem(XP,F);
! 269: R = GCD;
! 270: } else
! 271: R = 1;
! 272: TPMOD += time()[0]-T0;
! 273: return [R,F,XP];
! 274: }
! 275:
! 276: /*
! 277: Input : a square free polynomial F s.t.
! 278: all the irreducible factors of F
! 279: has the same degree D.
! 280: Output: D
! 281: */
! 282:
! 283: def meq_ed_ff(F,XP)
! 284: {
! 285: T0 = time()[0];
! 286: F = simp_ff(F);
! 287: F = F/LCOEF(F);
! 288: V = var(F);
! 289:
! 290: TAB = pwrtab_ff(F,XP);
! 291:
! 292: D = deg(F,V);
! 293: for ( I = 1, W = V, L = []; 2*I <= D; I++ ) {
! 294: lazy_lm(1);
! 295: for ( T = 0, K = 0; K <= deg(W,V); K++ )
! 296: if ( C = coef(W,K,V) )
! 297: T += TAB[K]*C;
! 298: lazy_lm(0);
! 299: W = simp_ff(T);
! 300: if ( W == V ) {
! 301: D = I; break;
! 302: }
! 303: }
! 304: TQMOD += time()[0]-T0;
! 305: return D;
! 306: }
! 307:
! 308: /*
! 309: Input : a square free polynomial F
! 310: an integer E
! 311: an array TAB
! 312: where all the irreducible factors of F has degree E
! 313: and TAB[i] = V^(i*Ord) mod F. (V=var(F), Ord=field order)
! 314: Output: a list containing all the irreducible factors of F
! 315: */
! 316:
! 317: def berlekamp_ff(F,E,TAB)
! 318: {
! 319: V = var(F);
! 320: N = deg(F,V);
! 321: Q = newmat(N,N);
! 322: for ( J = 0; J < N; J++ ) {
! 323: T = urem(TAB[J],F);
! 324: for ( I = 0; I < N; I++ ) {
! 325: Q[I][J] = coef(T,I);
! 326: }
! 327: }
! 328: for ( I = 0; I < N; I++ )
! 329: Q[I][I] -= simp_ff(1);
! 330: L = nullspace_ff(Q); MT = L[0]; IND = L[1];
! 331: NF0 = N/E;
! 332: PS = null_to_poly_ff(MT,IND,V);
! 333: R = newvect(NF0); R[0] = F/LCOEF(F);
! 334: for ( I = 1, NF = 1; NF < NF0 && I < NF0; I++ ) {
! 335: PSI = PS[I];
! 336: MP = minipoly_ff(PSI,F);
! 337: ROOT = find_root_ff(MP); NR = length(ROOT);
! 338: for ( J = 0; J < NF; J++ ) {
! 339: if ( deg(R[J],V) == E )
! 340: continue;
! 341: for ( K = 0; K < NR; K++ ) {
! 342: GCD = ugcd(R[J],PSI-ROOT[K]);
! 343: if ( deg(GCD,V) > 0 && deg(GCD,V) < deg(R[J],V) ) {
! 344: Q = sdiv(R[J],GCD);
! 345: R[J] = Q; R[NF++] = GCD;
! 346: }
! 347: }
! 348: }
! 349: }
! 350: return vtol(R);
! 351: }
! 352:
! 353: /*
! 354: Input : a matrix MT
! 355: an array IND
! 356: an indeterminate V
! 357: MT is a matrix after Gaussian elimination
! 358: IND[I] = 0 means that i-th column of MT represents a basis
! 359: element of the null space.
! 360: Output: an array R which contains all the basis element of
! 361: the null space of MT. Here, a basis element E is represented
! 362: as a polynomial P of V s.t. coef(P,i) = E[i].
! 363: */
! 364:
! 365: def null_to_poly_ff(MT,IND,V)
! 366: {
! 367: N = size(MT)[0];
! 368: for ( I = 0, J = 0; I < N; I++ )
! 369: if ( IND[I] )
! 370: J++;
! 371: R = newvect(J);
! 372: for ( I = 0, L = 0; I < N; I++ ) {
! 373: if ( !IND[I] )
! 374: continue;
! 375: for ( J = K = 0, T = 0; J < N; J++ )
! 376: if ( !IND[J] )
! 377: T += MT[K++][I]*V^J;
! 378: else if ( J == I )
! 379: T -= V^I;
! 380: R[L++] = simp_ff(T);
! 381: }
! 382: return R;
! 383: }
! 384:
! 385: /*
! 386: Input : a polynomial P, a polynomial F
! 387: Output: a minimal polynomial MP(V) of P mod F.
! 388: */
! 389:
! 390: def minipoly_ff(P,F)
! 391: {
! 392: V = var(P);
! 393: P0 = P1 = simp_ff(1);
! 394: L = [[P0,P0]];
! 395: while ( 1 ) {
! 396: /* P0 = V^K, P1 = P^K mod F */
! 397: P0 *= V;
! 398: P1 = urem(P*P1,F);
! 399: /*
! 400: NP0 = P0-c1L1_0-c2L2_0-...,
! 401: NP1 is a normal form w.r.t. [L1_1,L2_1,...]
! 402: NP1 = P1-c1L1_1-c2L2_1-...,
! 403: NP0 represents the normal form computation.
! 404: */
! 405: L1 = lnf_ff(P0,P1,L,V); NP0 = L1[0]; NP1 = L1[1];
! 406: if ( !NP1 )
! 407: return NP0;
! 408: else
! 409: L = lnf_insert([NP0,NP1],L,V);
! 410: }
! 411: }
! 412:
! 413: /*
! 414: Input ; a list of polynomials [P0,P1] = [V^K,P^K mod F]
! 415: a sorted list L=[[L1_0,L1_1],[L2_0,L2_1],...]
! 416: of previously computed pairs of polynomials
! 417: an indeterminate V
! 418: Output: a list of polynomials [NP0,NP1]
! 419: where NP1 = P1-c1L1_1-c2L2_1-...,
! 420: NP0 = P0-c1L1_0-c2L2_0-...,
! 421: NP1 is a normal form w.r.t. [L1_1,L2_1,...]
! 422: NP0 represents the normal form computation.
! 423: [L1_1,L_2_1,...] is sorted so that it is a triangular
! 424: linear basis s.t. deg(Li_1) > deg(Lj_1) for i<j.
! 425: */
! 426:
! 427: def lnf_ff(P0,P1,L,V)
! 428: {
! 429: NP0 = P0; NP1 = P1;
! 430: for ( T = L; T != []; T = cdr(T) ) {
! 431: Q = car(T);
! 432: D1 = deg(NP1,V);
! 433: if ( D1 == deg(Q[1],V) ) {
! 434: H = -coef(NP1,D1,V)/coef(Q[1],D1,V);
! 435: NP0 += Q[0]*H;
! 436: NP1 += Q[1]*H;
! 437: }
! 438: }
! 439: return [NP0,NP1];
! 440: }
! 441:
! 442: /*
! 443: Input : a pair of polynomial P=[P0,P1],
! 444: a list L,
! 445: an indeterminate V
! 446: Output: a list L1 s.t. L1 contains P and L
! 447: and L1 is sorted in the decreasing order
! 448: w.r.t. the degree of the second element
! 449: of elements in L1.
! 450: */
! 451:
! 452: def lnf_insert(P,L,V)
! 453: {
! 454: if ( L == [] )
! 455: return [P];
! 456: else {
! 457: P0 = car(L);
! 458: if ( deg(P0[1],V) > deg(P[1],V) )
! 459: return cons(P0,lnf_insert(P,cdr(L),V));
! 460: else
! 461: return cons(P,L);
! 462: }
! 463: }
! 464:
! 465: /*
! 466: Input : a square free polynomial F s.t.
! 467: all the irreducible factors of F
! 468: has the degree E.
! 469: Output: a list containing all the irreducible factors of F
! 470: */
! 471:
! 472: def c_z_ff(F,E)
! 473: {
! 474: Type = field_type_ff();
! 475: if ( Type == 1 || Type == 3 || Type == 4 || Type == 5 )
! 476: return c_z_lm(F,E);
! 477: else
! 478: return c_z_gf2n(F,E);
! 479: }
! 480:
! 481: /*
! 482: Input : a square free polynomial P s.t. P splits into linear factors
! 483: Output: a list containing all the root of P
! 484: */
! 485:
! 486: def find_root_ff(P)
! 487: {
! 488: V = var(P);
! 489: L = c_z_ff(P,1);
! 490: for ( T = L, U = []; T != []; T = cdr(T) ) {
! 491: S = car(T)/LCOEF(car(T)); U = cons(-coef(S,0,V),U);
! 492: }
! 493: return U;
! 494: }
! 495:
! 496: /*
! 497: Input : a square free polynomial F s.t.
! 498: all the irreducible factors of F
! 499: has the degree E.
! 500: Output: an irreducible factor of F
! 501: */
! 502:
! 503: def c_z_one_ff(F,E)
! 504: {
! 505: Type = field_type_ff();
! 506: if ( Type == 1 || Type == 3 || Type == 4 || Type == 5 )
! 507: return c_z_one_lm(F,E);
! 508: else
! 509: return c_z_one_gf2n(F,E);
! 510: }
! 511:
! 512: /*
! 513: Input : a square free polynomial P s.t. P splits into linear factors
! 514: Output: a list containing a root of P
! 515: */
! 516:
! 517: def find_one_root_ff(P)
! 518: {
! 519: V = var(P);
! 520: LF = c_z_one_ff(P,1);
! 521: U = -coef(LF/LCOEF(LF),0,V);
! 522: return [U];
! 523: }
! 524:
! 525: /*
! 526: Input : an integer N; an indeterminate V
! 527: Output: a polynomial F s.t. var(F) = V, deg(F) < N
! 528: and its coefs are random numbers in
! 529: the ground field.
! 530: */
! 531:
! 532: def randpoly_ff(N,V)
! 533: {
! 534: for ( I = 0, S = 0; I < N; I++ )
! 535: S += random_ff()*V^I;
! 536: return S;
! 537: }
! 538:
! 539: /*
! 540: Input : an integer N; an indeterminate V
! 541: Output: a monic polynomial F s.t. var(F) = V, deg(F) = N-1
! 542: and its coefs are random numbers in
! 543: the ground field except for the leading term.
! 544: */
! 545:
! 546: def monic_randpoly_ff(N,V)
! 547: {
! 548: for ( I = 0, N1 = N-1, S = 0; I < N1; I++ )
! 549: S += random_ff()*V^I;
! 550: return V^N1+S;
! 551: }
! 552:
! 553: /* GF(p) specific functions */
! 554:
! 555: /*
! 556: Input : a square free polynomial F s.t.
! 557: all the irreducible factors of F
! 558: has the degree E.
! 559: Output: a list containing all the irreducible factors of F
! 560: */
! 561:
! 562: def c_z_lm(F,E)
! 563: {
! 564: V = var(F);
! 565: N = deg(F,V);
! 566: if ( N == E )
! 567: return [F];
! 568: M = field_order_ff();
! 569: K = idiv(N,E);
! 570: L = [F];
! 571: while ( 1 ) {
! 572: W = monic_randpoly_ff(2*E,V);
! 573: T = generic_pwrmod_ff(W,F,idiv(M^E-1,2));
! 574: W = T-1;
! 575: if ( !W )
! 576: continue;
! 577: G = ugcd(F,W);
! 578: if ( deg(G,V) && deg(G,V) < N ) {
! 579: L1 = c_z_lm(G,E);
! 580: L2 = c_z_lm(sdiv(F,G),E);
! 581: return append(L1,L2);
! 582: }
! 583: }
! 584: }
! 585:
! 586: /*
! 587: Input : a square free polynomial F s.t.
! 588: all the irreducible factors of F
! 589: has the degree E.
! 590: Output: an irreducible factor of F
! 591: */
! 592:
! 593: def c_z_one_lm(F,E)
! 594: {
! 595: V = var(F);
! 596: N = deg(F,V);
! 597: if ( N == E )
! 598: return F;
! 599: M = field_order_ff();
! 600: K = idiv(N,E);
! 601: while ( 1 ) {
! 602: W = monic_randpoly_ff(2*E,V);
! 603: T = generic_pwrmod_ff(W,F,idiv(M^E-1,2));
! 604: W = T-1;
! 605: if ( W ) {
! 606: G = ugcd(F,W);
! 607: D = deg(G,V);
! 608: if ( D && D < N ) {
! 609: if ( 2*D <= N ) {
! 610: F1 = G; F2 = sdiv(F,G);
! 611: } else {
! 612: F2 = G; F1 = sdiv(F,G);
! 613: }
! 614: return c_z_one_lm(F1,E);
! 615: }
! 616: }
! 617: }
! 618: }
! 619:
! 620: /* GF(2^n) specific functions */
! 621:
! 622: /*
! 623: Input : a square free polynomial F s.t.
! 624: all the irreducible factors of F
! 625: has the degree E.
! 626: Output: a list containing all the irreducible factors of F
! 627: */
! 628:
! 629: def c_z_gf2n(F,E)
! 630: {
! 631: V = var(F);
! 632: N = deg(F,V);
! 633: if ( N == E )
! 634: return [F];
! 635: K = idiv(N,E);
! 636: L = [F];
! 637: while ( 1 ) {
! 638: W = randpoly_ff(2*E,V);
! 639: T = tracemod_gf2n(W,F,E);
! 640: W = T-1;
! 641: if ( !W )
! 642: continue;
! 643: G = ugcd(F,W);
! 644: if ( deg(G,V) && deg(G,V) < N ) {
! 645: L1 = c_z_gf2n(G,E);
! 646: L2 = c_z_gf2n(sdiv(F,G),E);
! 647: return append(L1,L2);
! 648: }
! 649: }
! 650: }
! 651:
! 652: /*
! 653: Input : a square free polynomial F s.t.
! 654: all the irreducible factors of F
! 655: has the degree E.
! 656: Output: an irreducible factor of F
! 657: */
! 658:
! 659: def c_z_one_gf2n(F,E)
! 660: {
! 661: V = var(F);
! 662: N = deg(F,V);
! 663: if ( N == E )
! 664: return F;
! 665: K = idiv(N,E);
! 666: while ( 1 ) {
! 667: W = randpoly_ff(2*E,V);
! 668: T = tracemod_gf2n(W,F,E);
! 669: W = T-1;
! 670: if ( W ) {
! 671: G = ugcd(F,W);
! 672: D = deg(G,V);
! 673: if ( D && D < N ) {
! 674: if ( 2*D <= N ) {
! 675: F1 = G; F2 = sdiv(F,G);
! 676: } else {
! 677: F2 = G; F1 = sdiv(F,G);
! 678: }
! 679: return c_z_one_gf2n(F1,E);
! 680: }
! 681: }
! 682: }
! 683: }
! 684:
! 685: /*
! 686: Input : an integer D
! 687: Output: an irreducible polynomial F over GF(2)
! 688: of degree D.
! 689: */
! 690:
! 691: def defpoly_mod2(D)
! 692: {
! 693: return gf2ntop(irredpoly_up2(D,0));
! 694: }
! 695:
! 696: def dummy_time() {
! 697: return [0,0,0,0];
! 698: }
! 699: end$
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[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 / asir2018 / lib