![[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
1.3 noro 26: * e-mail at risa-admin@sec.flab.fujitsu.co.jp of the detailed specification
1.2 noro 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: *
1.7 ! takayama 48: * $OpenXM: OpenXM_contrib2/asir2000/lib/fff,v 1.6 2001/09/03 07:01:09 noro Exp $
1.2 noro 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: */
1.7 ! takayama 59: module fff $
! 60: /* Empty for now. It will be used in a future. */
! 61: endmodule $
1.1 noro 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);
1.4 noro 118: FLAT /= LCOEF(FLAT);
1.1 noro 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);
1.4 noro 133: FLAT1 /= LCOEF(FLAT1);
1.1 noro 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();
1.6 noro 475: if ( Type == 1 || Type == 3 || Type == 4 || Type == 5 )
1.1 noro 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();
1.6 noro 506: if ( Type == 1 || Type == 3 || Type == 4 || Type == 5 )
1.1 noro 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$