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