[BACK]Return to up_gf2n.c CVS log [TXT][DIR] Up to [local] / OpenXM_contrib2 / asir2000 / engine

Annotation of OpenXM_contrib2/asir2000/engine/up_gf2n.c, Revision 1.2

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/engine/up_gf2n.c,v 1.1.1.1 1999/12/03 07:39:08 noro Exp $
        !            49: */
1.1       noro       50: #include "ca.h"
                     51: #include <math.h>
                     52:
                     53: extern int debug_up;
                     54: extern int up_lazy;
                     55: extern GEN_UP2 current_mod_gf2n;
                     56:
                     57: void squarep_gf2n(vl,n1,nr)
                     58: VL vl;
                     59: P n1;
                     60: P *nr;
                     61: {
                     62:        UP b1,br;
                     63:
                     64:        if ( !n1 )
                     65:                *nr = 0;
                     66:        else if ( OID(n1) == O_N )
                     67:                mulp(vl,n1,n1,nr);
                     68:        else {
                     69:                ptoup(n1,&b1);
                     70:                squareup_gf2n(b1,&br);
                     71:                uptop(br,nr);
                     72:        }
                     73: }
                     74:
                     75: void squareup_gf2n(n1,nr)
                     76: UP n1;
                     77: UP *nr;
                     78: {
                     79:        UP r;
                     80:        GF2N *c1,*c;
                     81:        int i,d1,d;
                     82:
                     83:        if ( !n1 )
                     84:                *nr = 0;
                     85:        else if ( !n1->d ) {
                     86:                *nr = r = UPALLOC(0); r->d = 0;
                     87:                squaregf2n((GF2N)n1->c[0],(GF2N *)(&r->c[0]));
                     88:        } else {
                     89:                d1 = n1->d;
                     90:                d = 2*d1;
                     91:                *nr = r = UPALLOC(d); r->d = d;
                     92:                c1 = (GF2N *)n1->c; c = (GF2N *)r->c;
                     93:                bzero((char *)c,(d+1)*sizeof(GF2N *));
                     94:                for ( i = 0; i <= d1; i++ )
                     95:                        squaregf2n(c1[i],&c[2*i]);
                     96:        }
                     97: }
                     98:
                     99: /* x^(2^n) mod f */
                    100:
                    101: void powermodup_gf2n(f,xp)
                    102: UP f;
                    103: UP *xp;
                    104: {
                    105:        UP x,t,invf;
                    106:        int k,n;
                    107:        GF2N lm;
                    108:        struct oEGT eg_sq,eg_rem,eg_mul,eg_inv,eg0,eg1,eg2;
                    109:
                    110:        n = degup2(current_mod_gf2n->dense);
                    111:        MKGF2N(ONEUP2,lm);
                    112:        x = UPALLOC(1); x->d = 1; x->c[1] = (Num)lm;
                    113:
                    114:        reverseup(f,f->d,&t);
                    115:        invmodup(t,f->d,&invf);
                    116:        for ( k = 0; k < n; k++ ) {
                    117:                squareup_gf2n(x,&t);
                    118:                rembymulup_special(t,f,invf,&x);
                    119: /*             remup(t,f,&x); */
                    120:        }
                    121:        *xp = x;
                    122: }
                    123:
                    124: /* g^d mod f */
                    125:
                    126: void generic_powermodup_gf2n(g,f,d,xp)
                    127: UP g,f;
                    128: Q d;
                    129: UP *xp;
                    130: {
                    131:        N e;
                    132:        UP x,y,t,invf,s;
                    133:        int k;
                    134:        GF2N lm;
                    135:
                    136:        e = NM(d);
                    137:        MKGF2N(ONEUP2,lm);
                    138:        y = UPALLOC(0); y->d = 0; y->c[0] = (Num)lm;
                    139:        remup(g,f,&x);
                    140:        if ( !x ) {
                    141:                *xp = !d ? y : 0;
                    142:                return;
                    143:        } else if ( !x->d ) {
                    144:                pwrup(x,d,xp);
                    145:                return;
                    146:        }
                    147:        reverseup(f,f->d,&t);
                    148:        invmodup(t,f->d,&invf);
                    149:        for ( k = n_bits(e)-1; k >= 0; k-- ) {
                    150:                squareup_gf2n(y,&t);
                    151:                rembymulup_special(t,f,invf,&s);
                    152:                y = s;
                    153:                if ( e->b[k/32] & (1<<(k%32)) ) {
                    154:                        mulup(y,x,&t);
                    155:                        remup(t,f,&s);
                    156:                        y = s;
                    157:                }
                    158:        }
                    159:        *xp = y;
                    160: }
                    161:
                    162: /* g+g^2+...+g^(2^(nd-1)) mod f; where e = deg(mod) */
                    163:
                    164: void tracemodup_gf2n(g,f,d,xp)
                    165: UP g,f;
                    166: Q d;
                    167: UP *xp;
                    168: {
                    169:        UP x,t,s,u,invf;
                    170:        int en,i;
                    171:
                    172:        en = QTOS(d)*degup2(current_mod_gf2n->dense);
                    173:        remup(g,f,&x);
                    174:        if ( !x ) {
                    175:                *xp = 0;
                    176:                return;
                    177:        }
                    178:        reverseup(f,f->d,&t);
                    179:        invmodup(t,f->d,&invf);
                    180:        for ( i = 1, t = s = x; i < en; i++ ) {
                    181:                squareup_gf2n(t,&u);
                    182:                rembymulup_special(u,f,invf,&t);
                    183:                addup(s,t,&u); s = u;
                    184:        }
                    185:        *xp = s;
                    186: }
                    187:
                    188: void tracemodup_gf2n_slow(g,f,d,xp)
                    189: UP g,f;
                    190: Q d;
                    191: UP *xp;
                    192: {
                    193:        UP x,t,s,u;
                    194:        int en,i;
                    195:
                    196:        en = QTOS(d)*degup2(current_mod_gf2n->dense);
                    197:        remup(g,f,&x);
                    198:        if ( !x ) {
                    199:                *xp = 0;
                    200:                return;
                    201:        }
                    202:        for ( i = 1, t = s = x; i < en; i++ ) {
                    203:                squareup_gf2n(t,&u);
                    204:                remup(u,f,&t);
                    205:                addup(s,t,&u); s = u;
                    206:        }
                    207:        *xp = s;
                    208: }
                    209:
                    210: static struct oEGT eg_trace_tab,eg_trace_mul;
                    211:
                    212: void tracemodup_gf2n_tab(g,f,d,xp)
                    213: UP g,f;
                    214: Q d;
                    215: UP *xp;
                    216: {
                    217:        UP x0,x2,t,s,u;
                    218:        int en,i;
                    219:        UP *tab;
                    220:        GF2N one;
                    221:        struct oEGT eg1,eg2;
                    222:
                    223:        en = QTOS(d)*degup2(current_mod_gf2n->dense);
                    224:        remup(g,f,&t); g = t;
                    225:        if ( !g ) {
                    226:                *xp = 0;
                    227:                return;
                    228:        }
                    229:
                    230:        MKGF2N(ONEUP2,one);
                    231:        x0 = UPALLOC(0); x0->d = 0; x0->c[0] = (Num)one;
                    232:        x2 = UPALLOC(2); x2->d = 2; x2->c[2] = (Num)one;
                    233:
                    234:        tab = (UP *)ALLOCA(en*sizeof(UP));
                    235:        tab[0] = x0;
                    236:        remup(x2,f,&tab[1]);
                    237:
                    238:        for ( i = 2; i < en; i++ ) {
                    239:                mulup(tab[i-1],tab[1],&t); remup(t,f,&tab[i]);
                    240:        }
                    241:
                    242:        for ( i = 1, t = s = g; i < en; i++ ) {
                    243:                square_rem_tab_up_gf2n(t,tab,&u); t = u;
                    244:                addup(s,t,&u); s = u;
                    245:        }
                    246:        *xp = s;
                    247: }
                    248:
                    249: void square_rem_tab_up_gf2n(f,tab,rp)
                    250: UP f;
                    251: UP *tab;
                    252: UP *rp;
                    253: {
                    254:        UP s,t,u,n;
                    255:        Num *c;
                    256:        int i,d;
                    257:
                    258:        n = UPALLOC(0); n->d = 0;
                    259:        if ( !f )
                    260:                *rp = 0;
                    261:        else {
                    262:                d = f->d; c = f->c;
                    263:                up_lazy = 1;
                    264:                for ( i = 0, s = 0; i <= d; i++ ) {
                    265:                        squaregf2n((GF2N)c[i],(GF2N *)(&n->c[0]));
                    266:                        mulup(tab[i],n,&t); addup(s,t,&u); s = u;
                    267:                }
                    268:                up_lazy = 0;
                    269:                simpup(s,rp);
                    270:        }
                    271: }
                    272:
                    273: void powertabup_gf2n(f,xp,tab)
                    274: UP f;
                    275: UP xp;
                    276: UP *tab;
                    277: {
                    278:        UP y,t,invf;
                    279:        int i,d;
                    280:        GF2N lm;
                    281:
                    282:        d = f->d;
                    283:        MKGF2N(ONEUP2,lm);
                    284:        y = UPALLOC(0); y->d = 0; y->c[0] = (Num)lm;
                    285:        tab[0] = y;
                    286:        tab[1] = xp;
                    287:
                    288:        reverseup(f,f->d,&t);
                    289:        invmodup(t,f->d,&invf);
                    290:
                    291:        for ( i = 2; i < d; i++ ) {
                    292:                if ( debug_up )
                    293:                        fprintf(stderr,".");
                    294:                if ( !(i%2) )
                    295:                        squareup_gf2n(tab[i/2],&t);
                    296:                else
                    297:                        kmulup(tab[i-1],xp,&t);
                    298:                rembymulup_special(t,f,invf,&tab[i]);
                    299: /*             remup(t,f,&tab[i]); */
                    300:        }
                    301: }
                    302:
                    303: void find_root_gf2n(f,r)
                    304: UP f;
                    305: GF2N *r;
                    306: {
                    307:        UP g,ut,c,t,h,rem;
                    308:        int n;
                    309:        GF2N rn;
                    310:        struct oEGT eg0,eg1,eg_trace;
                    311:
                    312:        n = degup2(current_mod_gf2n->dense);
                    313:        g = f;
                    314:        while ( g->d > 1 ) {
                    315:                ut = UPALLOC(1); ut->c[0] = 0;
                    316:                randomgf2n(&rn);
                    317:                if ( !rn )
                    318:                        continue;
                    319:                ut->c[1] = (Num)rn; ut->d = 1;
                    320:                tracemodup_gf2n_tab(ut,f,ONE,&c);
                    321:                gcdup(c,g,&h);
                    322:                if ( h->d && h->d < g->d ) {
                    323:                        if ( 2*h->d > g->d ) {
                    324:                                qrup(g,h,&t,&rem); g = t;
                    325:                                if ( rem )
                    326:                                        error("find_root_gf2n : cannot happen");
                    327:                        } else
                    328:                                g = h;
                    329:                }
                    330:                monicup(g,&t); g = t;
                    331:                printf("deg(g)=%d\n",g->d);
                    332:        }
                    333:        divgf2n((GF2N)g->c[0],(GF2N)g->c[1],r);
                    334: }

FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>