![[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|
Return to up_gf2n.c CVS log | Up to [local] / OpenXM_contrib2 / asir2000 / engine |
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.3 ! noro 48: * $OpenXM: OpenXM_contrib2/asir2000/engine/up_gf2n.c,v 1.2 2000/08/21 08:31:28 noro 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:
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: }