![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to gfs.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 gfs.c CVS log | Up to [local] / OpenXM_contrib2 / asir2000 / engine |
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 ligfsted,
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 ligfsted right to use the SOFTWARE hereunder, and FLL or any
11: * third party developer retains all rights, including but not ligfsted 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 acadegfsc, 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 pergfstted 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-adgfsn@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: *
1.5 ! noro 48: * $OpenXM: OpenXM_contrib2/asir2000/engine/gfs.c,v 1.4 2001/03/29 09:49:58 noro Exp $
1.1 noro 49: */
50: #include "ca.h"
51:
52: /* q = p^n */
53:
1.2 noro 54: P current_gfs_ext;
55: int current_gfs_p;
1.1 noro 56: int current_gfs_q;
57: int current_gfs_q1;
58: int *current_gfs_plus1;
59: int *current_gfs_ntoi;
60: int *current_gfs_iton;
61:
62: void chsgngfs();
1.2 noro 63: void generate_defpoly_um();
64:
65: void dec_um(p,a,u)
66: int p,a;
67: UM u;
68: {
69: int i;
70:
71: for ( i = 0; a; i++, a /= p )
72: COEF(u)[i] = a%p;
73: DEG(u) = i-1;
74: }
1.1 noro 75:
76: /*
1.2 noro 77: * an element of GF(p^n) f(x)=a(n-1)*x^(n-1)+...+a(0)
78: * is encodeded to f(p).
1.1 noro 79: * current_gfs_iton[i] = r^i mod p (i=0,...,p-2)
80: * current_gfs_iton[p-1] = 0
81: */
82:
83: void setmod_sf(p,n)
84: int p,n;
85: {
1.2 noro 86: int r,i,q1,q,t,t1;
87: UM dp;
1.1 noro 88:
1.2 noro 89: for ( i = 0, q = 1; i < n; i++ )
90: q *= p;
91: dp = UMALLOC(n);
92: generate_defpoly_um(p,n,dp);
93: r = generate_primitive_root_enc(p,n,dp);
94: current_gfs_p = p;
95: current_gfs_q = q;
96: current_gfs_q1 = q1 = q-1;
1.1 noro 97: if ( n > 1 )
1.2 noro 98: umtop(CO->v,dp,¤t_gfs_ext);
99: else
100: current_gfs_ext = 0;
101: current_gfs_iton = (int *)MALLOC(q1*sizeof(int));
102: current_gfs_iton[0] = 1;
103: for ( i = 1; i < q1; i++ )
104: current_gfs_iton[i] = mulremum_enc(p,n,dp,current_gfs_iton[i-1],r);
105:
106: current_gfs_ntoi = (int *)MALLOC(q*sizeof(int));
107: current_gfs_ntoi[0] = -1;
108: for ( i = 0; i < q1; i++ )
109: current_gfs_ntoi[current_gfs_iton[i]] = i;
110:
111: current_gfs_plus1 = (int *)MALLOC(q*sizeof(int));
112: for ( i = 0; i < q1; i++ ) {
113: t = current_gfs_iton[i];
114: /* add 1 to the constant part */
115: t1 = (t/p)*p+((t+1)%p);
116: current_gfs_plus1[i] = current_gfs_ntoi[t1];
1.1 noro 117: }
118: }
119:
1.2 noro 120: void generate_defpoly_um(p,n,dp)
121: int p,n;
122: UM dp;
1.1 noro 123: {
1.2 noro 124: int i,j,a,c,q;
125: UM wf,wdf,wgcd;
1.1 noro 126:
1.2 noro 127: wf = W_UMALLOC(n);
128: wdf = W_UMALLOC(n);
129: wgcd = W_UMALLOC(n);
130: COEF(dp)[n] = 1;
131: DEG(dp) = n;
132: for ( i = 0, q = 1; i < n; i++ )
133: q *= p;
134: for ( i = 0; i < q; i++ ) {
135: for ( j = 0, a = i; a; j++, a /= p )
136: COEF(dp)[j] = a%p;
137: for ( ; j < n; j++ )
138: COEF(dp)[j] = 0;
139: cpyum(dp,wf);
140: diffum(p,dp,wdf);
141: gcdum(p,wf,wdf,wgcd);
142: if ( DEG(wgcd) >= 1 )
143: continue;
144: mini(p,dp,wf);
145: if ( DEG(wf) <= 0 )
146: return;
147: }
148: }
149:
150: int generate_primitive_root_enc(p,n,dp)
151: int p,n;
152: UM dp;
153: {
154: int i,r,rj,j,q;
155:
1.5 ! noro 156: if ( p == 2 && n == 1 )
! 157: return 1;
! 158:
1.2 noro 159: for ( i = 0, q = 1; i < n; i++ )
160: q *= p;
161: for ( r = n==1?2:p; r < q; r++ ) {
1.1 noro 162: rj = r;
1.2 noro 163: for ( j = 1; j < q-1 && rj != 1; j++ )
164: rj = mulremum_enc(p,n,dp,rj,r);
165: if ( j == q-1 )
1.1 noro 166: return r;
167: }
1.2 noro 168: }
169:
170: /* [a(p)]*[b(p)] in GF(p^n) -> [a(x)*b(x) mod dp(x)]_{x->p} */
171:
172: int mulremum_enc(p,n,dp,a,b)
173: int p,n;
174: UM dp;
175: int a,b;
176: {
177: int i,dr,r;
178: UM wa,wb,wc,wq;
179:
180: if ( n == 1 )
181: return (a*b)%p;
182: if ( !a || !b )
183: return 0;
184:
185: wa = W_UMALLOC(n);
186: dec_um(p,a,wa);
187:
188: wb = W_UMALLOC(n);
189: dec_um(p,b,wb);
190:
191: wc = W_UMALLOC(2*n);
192: wq = W_UMALLOC(2*n);
193: mulum(p,wa,wb,wc);
194: dr = divum(p,wc,dp,wq);
195: for ( i = dr, r = 0; i >= 0; i-- )
196: r = r*p+COEF(wc)[i];
197: return r;
1.5 ! noro 198: }
! 199:
! 200: void gfs_galois_action(a,e,c)
! 201: GFS a;
! 202: Q e;
! 203: GFS *c;
! 204: {
! 205: Q p;
! 206: int i,k;
! 207: GFS t,s;
! 208:
! 209: t = a;
! 210: k = QTOS(e);
! 211: STOQ(current_gfs_p,p);
! 212: for ( i = 0; i < k; i++ ) {
! 213: pwrgfs(t,p,&s); t = s;
! 214: }
! 215: *c = t;
! 216: }
! 217:
! 218: void qtogfs(a,c)
! 219: Q a;
! 220: GFS *c;
! 221: {
! 222: int s;
! 223:
! 224: s = QTOS(a)%current_gfs_q;
! 225: if ( s < 0 )
! 226: s += current_gfs_q;
! 227: if ( !s )
! 228: *c = 0;
! 229: else
! 230: MKGFS(current_gfs_ntoi[s],*c);
1.1 noro 231: }
232:
233: void mqtogfs(a,c)
234: MQ a;
235: GFS *c;
236: {
237: if ( !a )
238: *c = 0;
239: else {
240: MKGFS(current_gfs_ntoi[CONT(a)],*c);
241: }
242: }
243:
244: void gfstomq(a,c)
245: GFS a;
246: MQ *c;
247: {
248: if ( !a )
249: *c = 0;
250: else {
251: UTOMQ(current_gfs_iton[CONT(a)],*c);
252: }
253: }
254:
255: void ntogfs(a,b)
256: Obj a;
257: GFS *b;
258: {
259: P t;
260:
261: if ( !current_gfs_q1 )
262: error("addgfs : current_gfs_q is not set");
263: if ( !a || (OID(a)==O_N && NID(a) == N_GFS) )
264: *b = (GFS)a;
265: else if ( OID(a) == O_N && NID(a) == N_M )
266: mqtogfs(a,b);
267: else if ( OID(a) == O_N && NID(a) == N_Q ) {
1.4 noro 268: ptomp(current_gfs_p,(P)a,&t); mqtogfs(t,b);
1.1 noro 269: } else
270: error("ntogfs : invalid argument");
271: }
272:
273: void addgfs(a,b,c)
274: GFS a,b;
275: GFS *c;
276: {
277: int ai,bi,ci;
278: GFS z;
279:
280: ntogfs(a,&z); a = z;
281: ntogfs(b,&z); b = z;
282: if ( !a )
283: *c = b;
284: else if ( !b )
285: *c = a;
286: else {
287: ai = CONT(a); bi = CONT(b);
288: if ( ai > bi ) {
289: /* tab[ai]+tab[bi] = tab[bi](tab[ai-bi]+1) */
290: ci = current_gfs_plus1[ai-bi];
291: if ( ci < 0 )
292: *c = 0;
293: else {
294: ci += bi;
295: if ( ci >= current_gfs_q1 )
296: ci -= current_gfs_q1;
297: MKGFS(ci,*c);
298: }
299: } else {
300: /* tab[ai]+tab[bi] = tab[ai](tab[bi-ai]+1) */
301: ci = current_gfs_plus1[bi-ai];
302: if ( ci < 0 )
303: *c = 0;
304: else {
305: ci += ai;
306: if ( ci >= current_gfs_q1 )
307: ci -= current_gfs_q1;
308: MKGFS(ci,*c);
309: }
310: }
311: }
312: }
313:
314: void subgfs(a,b,c)
315: GFS a,b;
316: GFS *c;
317: {
318: GFS t,z;
319:
320: ntogfs(a,&z); a = z;
321: ntogfs(b,&z); b = z;
322: if ( !b )
323: *c = a;
324: else {
325: chsgngfs(b,&t);
326: addgfs(a,t,c);
327: }
328: }
329:
330: void mulgfs(a,b,c)
331: GFS a,b;
332: GFS *c;
333: {
334: int ai;
335: GFS z;
336:
337: ntogfs(a,&z); a = z;
338: ntogfs(b,&z); b = z;
339: if ( !a || !b )
340: *c = 0;
341: else {
342: ai = CONT(a) + CONT(b);
343: if ( ai >= current_gfs_q1 )
344: ai -= current_gfs_q1;
345: MKGFS(ai,*c);
346: }
347: }
348:
349: void divgfs(a,b,c)
350: GFS a,b;
351: GFS *c;
352: {
353: int ai;
354: GFS z;
355:
356: ntogfs(a,&z); a = z;
357: ntogfs(b,&z); b = z;
358: if ( !b )
359: error("divgfs : division by 0");
360: else if ( !a )
361: *c = 0;
362: else {
363: ai = CONT(a) - CONT(b);
364: if ( ai < 0 )
365: ai += current_gfs_q1;
366: MKGFS(ai,*c);
367: }
368: }
369:
370: void chsgngfs(a,c)
371: GFS a,*c;
372: {
373: int ai;
374: GFS z;
375:
376: ntogfs(a,&z); a = z;
377: if ( !a )
378: *c = 0;
379: else if ( current_gfs_q1&1 )
380: *c = a;
381: else {
382: /* r^((q-1)/2) = -1 */
383: ai = CONT(a)+(current_gfs_q1>>1);
384: if ( ai >= current_gfs_q1 )
385: ai -= current_gfs_q1;
386: MKGFS(ai,*c);
387: }
388: }
389:
390: void pwrgfs(a,b,c)
391: GFS a;
392: Q b;
393: GFS *c;
394: {
395: N an,tn,rn;
396: GFS t,s,z;
397:
398: ntogfs(a,&z); a = z;
399: if ( !b )
400: MKGFS(0,*c);
401: else if ( !a )
402: *c = 0;
403: else {
404: STON(CONT(a),an); muln(an,NM(b),&tn);
405: STON(current_gfs_q1,an); remn(tn,an,&rn);
406: if ( !rn )
407: MKGFS(0,*c);
408: else if ( SGN(b) > 0 )
409: MKGFS(BD(rn)[0],*c);
410: else {
411: MKGFS(0,t);
412: MKGFS(BD(rn)[0],s);
413: divgfs(t,s,c);
414: }
415: }
416: }
417:
418: int cmpgfs(a,b)
419: GFS a,b;
420: {
421: GFS z;
422:
423: ntogfs(a,&z); a = z;
424: if ( !a )
425: return !b ? 0 : -1;
426: else
427: if ( !b )
428: return 1;
429: else {
430: if ( CONT(a) > CONT(b) )
431: return 1;
432: else if ( CONT(a) < CONT(b) )
433: return -1;
434: else
435: return 0;
436: }
1.3 noro 437: }
438:
439: void randomgfs(r)
440: GFS *r;
441: {
442: unsigned int t;
443:
444: if ( !current_gfs_q1 )
445: error("addgfs : current_gfs_q is not set");
446: t = mt_genrand()%current_gfs_q;
447: if ( !t )
448: *r = 0;
449: else {
450: if ( t == current_gfs_q1 )
451: t = 0;
452: MKGFS(t,*r);
453: }
1.1 noro 454: }