[BACK]Return to fff CVS log [TXT][DIR] Up to [local] / OpenXM_contrib2 / asir2018 / lib

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>