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