Annotation of OpenXM_contrib2/asir2000/engine/up_gf2n.c, Revision 1.7
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 ! noro 48: * $OpenXM: OpenXM_contrib2/asir2000/engine/up_gf2n.c,v 1.6 2015/08/14 13:51:55 fujimoto Exp $
1.2 noro 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:
1.4 noro 57: void squarep_gf2n(VL vl,P n1,P *nr)
1.1 noro 58: {
1.7 ! noro 59: UP b1,br;
1.1 noro 60:
1.7 ! noro 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: }
1.1 noro 70: }
71:
1.4 noro 72: void squareup_gf2n(UP n1,UP *nr)
1.1 noro 73: {
1.7 ! noro 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: }
1.1 noro 92: }
93:
94: /* x^(2^n) mod f */
95:
1.4 noro 96: void powermodup_gf2n(UP f,UP *xp)
1.1 noro 97: {
1.7 ! noro 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;
1.1 noro 114: }
115:
116: /* g^d mod f */
117:
1.4 noro 118: void generic_powermodup_gf2n(UP g,UP f,Q d,UP *xp)
1.1 noro 119: {
1.7 ! noro 120: N e;
! 121: UP x,y,t,invf,s;
! 122: int k;
! 123: GF2N lm;
! 124:
! 125: e = NM(d);
! 126: MKGF2N(ONEUP2,lm);
! 127: y = UPALLOC(0); y->d = 0; y->c[0] = (Num)lm;
! 128: remup(g,f,&x);
! 129: if ( !x ) {
! 130: *xp = !d ? y : 0;
! 131: return;
! 132: } else if ( !x->d ) {
! 133: pwrup(x,d,xp);
! 134: return;
! 135: }
! 136: reverseup(f,f->d,&t);
! 137: invmodup(t,f->d,&invf);
! 138: for ( k = n_bits(e)-1; k >= 0; k-- ) {
! 139: squareup_gf2n(y,&t);
! 140: rembymulup_special(t,f,invf,&s);
! 141: y = s;
! 142: if ( e->b[k/32] & (1<<(k%32)) ) {
! 143: mulup(y,x,&t);
! 144: remup(t,f,&s);
! 145: y = s;
! 146: }
! 147: }
! 148: *xp = y;
1.1 noro 149: }
150:
151: /* g+g^2+...+g^(2^(nd-1)) mod f; where e = deg(mod) */
152:
1.4 noro 153: void tracemodup_gf2n(UP g,UP f,Q d,UP *xp)
1.1 noro 154: {
1.7 ! noro 155: UP x,t,s,u,invf;
! 156: int en,i;
1.1 noro 157:
1.7 ! noro 158: en = QTOS(d)*degup2(current_mod_gf2n->dense);
! 159: remup(g,f,&x);
! 160: if ( !x ) {
! 161: *xp = 0;
! 162: return;
! 163: }
! 164: reverseup(f,f->d,&t);
! 165: invmodup(t,f->d,&invf);
! 166: for ( i = 1, t = s = x; i < en; i++ ) {
! 167: squareup_gf2n(t,&u);
! 168: rembymulup_special(u,f,invf,&t);
! 169: addup(s,t,&u); s = u;
! 170: }
! 171: *xp = s;
1.1 noro 172: }
173:
1.4 noro 174: void tracemodup_gf2n_slow(UP g,UP f,Q d,UP *xp)
1.1 noro 175: {
1.7 ! noro 176: UP x,t,s,u;
! 177: int en,i;
1.1 noro 178:
1.7 ! noro 179: en = QTOS(d)*degup2(current_mod_gf2n->dense);
! 180: remup(g,f,&x);
! 181: if ( !x ) {
! 182: *xp = 0;
! 183: return;
! 184: }
! 185: for ( i = 1, t = s = x; i < en; i++ ) {
! 186: squareup_gf2n(t,&u);
! 187: remup(u,f,&t);
! 188: addup(s,t,&u); s = u;
! 189: }
! 190: *xp = s;
1.1 noro 191: }
192:
1.4 noro 193: void tracemodup_gf2n_tab(UP g,UP f,Q d,UP *xp)
1.1 noro 194: {
1.7 ! noro 195: UP x0,x2,t,s,u;
! 196: int en,i;
! 197: UP *tab;
! 198: GF2N one;
! 199:
! 200: en = QTOS(d)*degup2(current_mod_gf2n->dense);
! 201: remup(g,f,&t); g = t;
! 202: if ( !g ) {
! 203: *xp = 0;
! 204: return;
! 205: }
! 206:
! 207: MKGF2N(ONEUP2,one);
! 208: x0 = UPALLOC(0); x0->d = 0; x0->c[0] = (Num)one;
! 209: x2 = UPALLOC(2); x2->d = 2; x2->c[2] = (Num)one;
! 210:
! 211: tab = (UP *)ALLOCA(en*sizeof(UP));
! 212: tab[0] = x0;
! 213: remup(x2,f,&tab[1]);
! 214:
! 215: for ( i = 2; i < en; i++ ) {
! 216: mulup(tab[i-1],tab[1],&t); remup(t,f,&tab[i]);
! 217: }
! 218:
! 219: for ( i = 1, t = s = g; i < en; i++ ) {
! 220: square_rem_tab_up_gf2n(t,tab,&u); t = u;
! 221: addup(s,t,&u); s = u;
! 222: }
! 223: *xp = s;
1.1 noro 224: }
225:
1.4 noro 226: void square_rem_tab_up_gf2n(UP f,UP *tab,UP *rp)
1.1 noro 227: {
1.7 ! noro 228: UP s,t,u,n;
! 229: Num *c;
! 230: int i,d;
! 231:
! 232: n = UPALLOC(0); n->d = 0;
! 233: if ( !f )
! 234: *rp = 0;
! 235: else {
! 236: d = f->d; c = f->c;
! 237: up_lazy = 1;
! 238: for ( i = 0, s = 0; i <= d; i++ ) {
! 239: squaregf2n((GF2N)c[i],(GF2N *)(&n->c[0]));
! 240: mulup(tab[i],n,&t); addup(s,t,&u); s = u;
! 241: }
! 242: up_lazy = 0;
! 243: simpup(s,rp);
! 244: }
1.1 noro 245: }
246:
1.4 noro 247: void powertabup_gf2n(UP f,UP xp,UP *tab)
1.1 noro 248: {
1.7 ! noro 249: UP y,t,invf;
! 250: int i,d;
! 251: GF2N lm;
! 252:
! 253: d = f->d;
! 254: MKGF2N(ONEUP2,lm);
! 255: y = UPALLOC(0); y->d = 0; y->c[0] = (Num)lm;
! 256: tab[0] = y;
! 257: tab[1] = xp;
! 258:
! 259: reverseup(f,f->d,&t);
! 260: invmodup(t,f->d,&invf);
! 261:
! 262: for ( i = 2; i < d; i++ ) {
! 263: if ( debug_up ){
! 264: fprintf(stderr,".");
! 265: }
! 266: if ( !(i%2) )
! 267: squareup_gf2n(tab[i/2],&t);
! 268: else
! 269: kmulup(tab[i-1],xp,&t);
! 270: rembymulup_special(t,f,invf,&tab[i]);
! 271: /* remup(t,f,&tab[i]); */
! 272: }
1.1 noro 273: }
274:
1.4 noro 275: void find_root_gf2n(UP f,GF2N *r)
1.1 noro 276: {
1.7 ! noro 277: UP g,ut,c,t,h,rem;
! 278: int n;
! 279: GF2N rn;
! 280:
! 281: n = degup2(current_mod_gf2n->dense);
! 282: g = f;
! 283: while ( g->d > 1 ) {
! 284: ut = UPALLOC(1); ut->c[0] = 0;
! 285: randomgf2n(&rn);
! 286: if ( !rn )
! 287: continue;
! 288: ut->c[1] = (Num)rn; ut->d = 1;
! 289: tracemodup_gf2n_tab(ut,f,ONE,&c);
! 290: gcdup(c,g,&h);
! 291: if ( h->d && h->d < g->d ) {
! 292: if ( 2*h->d > g->d ) {
! 293: qrup(g,h,&t,&rem); g = t;
! 294: if ( rem )
! 295: error("find_root_gf2n : cannot happen");
! 296: } else
! 297: g = h;
! 298: }
! 299: monicup(g,&t); g = t;
! 300: printf("deg(g)=%d\n",g->d);
! 301: }
! 302: divgf2n((GF2N)g->c[0],(GF2N)g->c[1],r);
1.1 noro 303: }
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 / asir2000 / engine