Annotation of OpenXM_contrib2/asir2018/engine/up_gf2n.c, 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: #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 vl,P n1,P *nr)
! 58: {
! 59: UP b1,br;
! 60:
! 61: if ( !n1 )
! 62: *nr = 0;
! 63: else if ( OID(n1) == O_N )
! 64: mulp(vl,n1,n1,nr);
! 65: else {
! 66: ptoup(n1,&b1);
! 67: squareup_gf2n(b1,&br);
! 68: uptop(br,nr);
! 69: }
! 70: }
! 71:
! 72: void squareup_gf2n(UP n1,UP *nr)
! 73: {
! 74: UP r;
! 75: GF2N *c1,*c;
! 76: int i,d1,d;
! 77:
! 78: if ( !n1 )
! 79: *nr = 0;
! 80: else if ( !n1->d ) {
! 81: *nr = r = UPALLOC(0); r->d = 0;
! 82: squaregf2n((GF2N)n1->c[0],(GF2N *)(&r->c[0]));
! 83: } else {
! 84: d1 = n1->d;
! 85: d = 2*d1;
! 86: *nr = r = UPALLOC(d); r->d = d;
! 87: c1 = (GF2N *)n1->c; c = (GF2N *)r->c;
! 88: bzero((char *)c,(d+1)*sizeof(GF2N *));
! 89: for ( i = 0; i <= d1; i++ )
! 90: squaregf2n(c1[i],&c[2*i]);
! 91: }
! 92: }
! 93:
! 94: /* x^(2^n) mod f */
! 95:
! 96: void powermodup_gf2n(UP f,UP *xp)
! 97: {
! 98: UP x,t,invf;
! 99: int k,n;
! 100: GF2N lm;
! 101:
! 102: n = degup2(current_mod_gf2n->dense);
! 103: MKGF2N(ONEUP2,lm);
! 104: x = UPALLOC(1); x->d = 1; x->c[1] = (Num)lm;
! 105:
! 106: reverseup(f,f->d,&t);
! 107: invmodup(t,f->d,&invf);
! 108: for ( k = 0; k < n; k++ ) {
! 109: squareup_gf2n(x,&t);
! 110: rembymulup_special(t,f,invf,&x);
! 111: /* remup(t,f,&x); */
! 112: }
! 113: *xp = x;
! 114: }
! 115:
! 116: /* g^d mod f */
! 117:
! 118: void generic_powermodup_gf2n(UP g,UP f,Z e,UP *xp)
! 119: {
! 120: UP x,y,t,invf,s;
! 121: int k;
! 122: GF2N lm;
! 123:
! 124: MKGF2N(ONEUP2,lm);
! 125: y = UPALLOC(0); y->d = 0; y->c[0] = (Num)lm;
! 126: remup(g,f,&x);
! 127: if ( !x ) {
! 128: *xp = !e ? y : 0;
! 129: return;
! 130: } else if ( !x->d ) {
! 131: pwrup(x,e,xp);
! 132: return;
! 133: }
! 134: reverseup(f,f->d,&t);
! 135: invmodup(t,f->d,&invf);
! 136: for ( k = z_bits((Q)e)-1; k >= 0; k-- ) {
! 137: squareup_gf2n(y,&t);
! 138: rembymulup_special(t,f,invf,&s);
! 139: y = s;
! 140: if ( mpz_tstbit(BDY(e),k) ) {
! 141: mulup(y,x,&t);
! 142: remup(t,f,&s);
! 143: y = s;
! 144: }
! 145: }
! 146: *xp = y;
! 147: }
! 148:
! 149: /* g+g^2+...+g^(2^(nd-1)) mod f; where e = deg(mod) */
! 150:
! 151: void tracemodup_gf2n(UP g,UP f,Z d,UP *xp)
! 152: {
! 153: UP x,t,s,u,invf;
! 154: int en,i;
! 155:
! 156: en = QTOS(d)*degup2(current_mod_gf2n->dense);
! 157: remup(g,f,&x);
! 158: if ( !x ) {
! 159: *xp = 0;
! 160: return;
! 161: }
! 162: reverseup(f,f->d,&t);
! 163: invmodup(t,f->d,&invf);
! 164: for ( i = 1, t = s = x; i < en; i++ ) {
! 165: squareup_gf2n(t,&u);
! 166: rembymulup_special(u,f,invf,&t);
! 167: addup(s,t,&u); s = u;
! 168: }
! 169: *xp = s;
! 170: }
! 171:
! 172: void tracemodup_gf2n_slow(UP g,UP f,Z d,UP *xp)
! 173: {
! 174: UP x,t,s,u;
! 175: int en,i;
! 176:
! 177: en = QTOS(d)*degup2(current_mod_gf2n->dense);
! 178: remup(g,f,&x);
! 179: if ( !x ) {
! 180: *xp = 0;
! 181: return;
! 182: }
! 183: for ( i = 1, t = s = x; i < en; i++ ) {
! 184: squareup_gf2n(t,&u);
! 185: remup(u,f,&t);
! 186: addup(s,t,&u); s = u;
! 187: }
! 188: *xp = s;
! 189: }
! 190:
! 191: void tracemodup_gf2n_tab(UP g,UP f,Z d,UP *xp)
! 192: {
! 193: UP x0,x2,t,s,u;
! 194: int en,i;
! 195: UP *tab;
! 196: GF2N one;
! 197:
! 198: en = QTOS(d)*degup2(current_mod_gf2n->dense);
! 199: remup(g,f,&t); g = t;
! 200: if ( !g ) {
! 201: *xp = 0;
! 202: return;
! 203: }
! 204:
! 205: MKGF2N(ONEUP2,one);
! 206: x0 = UPALLOC(0); x0->d = 0; x0->c[0] = (Num)one;
! 207: x2 = UPALLOC(2); x2->d = 2; x2->c[2] = (Num)one;
! 208:
! 209: tab = (UP *)ALLOCA(en*sizeof(UP));
! 210: tab[0] = x0;
! 211: remup(x2,f,&tab[1]);
! 212:
! 213: for ( i = 2; i < en; i++ ) {
! 214: mulup(tab[i-1],tab[1],&t); remup(t,f,&tab[i]);
! 215: }
! 216:
! 217: for ( i = 1, t = s = g; i < en; i++ ) {
! 218: square_rem_tab_up_gf2n(t,tab,&u); t = u;
! 219: addup(s,t,&u); s = u;
! 220: }
! 221: *xp = s;
! 222: }
! 223:
! 224: void square_rem_tab_up_gf2n(UP f,UP *tab,UP *rp)
! 225: {
! 226: UP s,t,u,n;
! 227: Num *c;
! 228: int i,d;
! 229:
! 230: n = UPALLOC(0); n->d = 0;
! 231: if ( !f )
! 232: *rp = 0;
! 233: else {
! 234: d = f->d; c = f->c;
! 235: up_lazy = 1;
! 236: for ( i = 0, s = 0; i <= d; i++ ) {
! 237: squaregf2n((GF2N)c[i],(GF2N *)(&n->c[0]));
! 238: mulup(tab[i],n,&t); addup(s,t,&u); s = u;
! 239: }
! 240: up_lazy = 0;
! 241: simpup(s,rp);
! 242: }
! 243: }
! 244:
! 245: void powertabup_gf2n(UP f,UP xp,UP *tab)
! 246: {
! 247: UP y,t,invf;
! 248: int i,d;
! 249: GF2N lm;
! 250:
! 251: d = f->d;
! 252: MKGF2N(ONEUP2,lm);
! 253: y = UPALLOC(0); y->d = 0; y->c[0] = (Num)lm;
! 254: tab[0] = y;
! 255: tab[1] = xp;
! 256:
! 257: reverseup(f,f->d,&t);
! 258: invmodup(t,f->d,&invf);
! 259:
! 260: for ( i = 2; i < d; i++ ) {
! 261: if ( debug_up ){
! 262: fprintf(stderr,".");
! 263: }
! 264: if ( !(i%2) )
! 265: squareup_gf2n(tab[i/2],&t);
! 266: else
! 267: kmulup(tab[i-1],xp,&t);
! 268: rembymulup_special(t,f,invf,&tab[i]);
! 269: /* remup(t,f,&tab[i]); */
! 270: }
! 271: }
! 272:
! 273: void find_root_gf2n(UP f,GF2N *r)
! 274: {
! 275: UP g,ut,c,t,h,rem;
! 276: int n;
! 277: GF2N rn;
! 278:
! 279: n = degup2(current_mod_gf2n->dense);
! 280: g = f;
! 281: while ( g->d > 1 ) {
! 282: ut = UPALLOC(1); ut->c[0] = 0;
! 283: randomgf2n(&rn);
! 284: if ( !rn )
! 285: continue;
! 286: ut->c[1] = (Num)rn; ut->d = 1;
! 287: tracemodup_gf2n_tab(ut,f,ONE,&c);
! 288: gcdup(c,g,&h);
! 289: if ( h->d && h->d < g->d ) {
! 290: if ( 2*h->d > g->d ) {
! 291: qrup(g,h,&t,&rem); g = t;
! 292: if ( rem )
! 293: error("find_root_gf2n : cannot happen");
! 294: } else
! 295: g = h;
! 296: }
! 297: monicup(g,&t); g = t;
! 298: printf("deg(g)=%d\n",g->d);
! 299: }
! 300: divgf2n((GF2N)g->c[0],(GF2N)g->c[1],r);
! 301: }
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to up_gf2n.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [local] / OpenXM_contrib2 / asir2018 / engine