![[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.4 ! noro 48: * $OpenXM: OpenXM_contrib2/asir2000/engine/gfs.c,v 1.3 2001/03/14 06:27:57 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:
156: for ( i = 0, q = 1; i < n; i++ )
157: q *= p;
158: for ( r = n==1?2:p; r < q; r++ ) {
1.1 noro 159: rj = r;
1.2 noro 160: for ( j = 1; j < q-1 && rj != 1; j++ )
161: rj = mulremum_enc(p,n,dp,rj,r);
162: if ( j == q-1 )
1.1 noro 163: return r;
164: }
1.2 noro 165: }
166:
167: /* [a(p)]*[b(p)] in GF(p^n) -> [a(x)*b(x) mod dp(x)]_{x->p} */
168:
169: int mulremum_enc(p,n,dp,a,b)
170: int p,n;
171: UM dp;
172: int a,b;
173: {
174: int i,dr,r;
175: UM wa,wb,wc,wq;
176:
177: if ( n == 1 )
178: return (a*b)%p;
179: if ( !a || !b )
180: return 0;
181:
182: wa = W_UMALLOC(n);
183: dec_um(p,a,wa);
184:
185: wb = W_UMALLOC(n);
186: dec_um(p,b,wb);
187:
188: wc = W_UMALLOC(2*n);
189: wq = W_UMALLOC(2*n);
190: mulum(p,wa,wb,wc);
191: dr = divum(p,wc,dp,wq);
192: for ( i = dr, r = 0; i >= 0; i-- )
193: r = r*p+COEF(wc)[i];
194: return r;
1.1 noro 195: }
196:
197: void mqtogfs(a,c)
198: MQ a;
199: GFS *c;
200: {
201: if ( !a )
202: *c = 0;
203: else {
204: MKGFS(current_gfs_ntoi[CONT(a)],*c);
205: }
206: }
207:
208: void gfstomq(a,c)
209: GFS a;
210: MQ *c;
211: {
212: if ( !a )
213: *c = 0;
214: else {
215: UTOMQ(current_gfs_iton[CONT(a)],*c);
216: }
217: }
218:
219: void ntogfs(a,b)
220: Obj a;
221: GFS *b;
222: {
223: P t;
224:
225: if ( !current_gfs_q1 )
226: error("addgfs : current_gfs_q is not set");
227: if ( !a || (OID(a)==O_N && NID(a) == N_GFS) )
228: *b = (GFS)a;
229: else if ( OID(a) == O_N && NID(a) == N_M )
230: mqtogfs(a,b);
231: else if ( OID(a) == O_N && NID(a) == N_Q ) {
1.4 ! noro 232: ptomp(current_gfs_p,(P)a,&t); mqtogfs(t,b);
1.1 noro 233: } else
234: error("ntogfs : invalid argument");
235: }
236:
237: void addgfs(a,b,c)
238: GFS a,b;
239: GFS *c;
240: {
241: int ai,bi,ci;
242: GFS z;
243:
244: ntogfs(a,&z); a = z;
245: ntogfs(b,&z); b = z;
246: if ( !a )
247: *c = b;
248: else if ( !b )
249: *c = a;
250: else {
251: ai = CONT(a); bi = CONT(b);
252: if ( ai > bi ) {
253: /* tab[ai]+tab[bi] = tab[bi](tab[ai-bi]+1) */
254: ci = current_gfs_plus1[ai-bi];
255: if ( ci < 0 )
256: *c = 0;
257: else {
258: ci += bi;
259: if ( ci >= current_gfs_q1 )
260: ci -= current_gfs_q1;
261: MKGFS(ci,*c);
262: }
263: } else {
264: /* tab[ai]+tab[bi] = tab[ai](tab[bi-ai]+1) */
265: ci = current_gfs_plus1[bi-ai];
266: if ( ci < 0 )
267: *c = 0;
268: else {
269: ci += ai;
270: if ( ci >= current_gfs_q1 )
271: ci -= current_gfs_q1;
272: MKGFS(ci,*c);
273: }
274: }
275: }
276: }
277:
278: void subgfs(a,b,c)
279: GFS a,b;
280: GFS *c;
281: {
282: GFS t,z;
283:
284: ntogfs(a,&z); a = z;
285: ntogfs(b,&z); b = z;
286: if ( !b )
287: *c = a;
288: else {
289: chsgngfs(b,&t);
290: addgfs(a,t,c);
291: }
292: }
293:
294: void mulgfs(a,b,c)
295: GFS a,b;
296: GFS *c;
297: {
298: int ai;
299: GFS z;
300:
301: ntogfs(a,&z); a = z;
302: ntogfs(b,&z); b = z;
303: if ( !a || !b )
304: *c = 0;
305: else {
306: ai = CONT(a) + CONT(b);
307: if ( ai >= current_gfs_q1 )
308: ai -= current_gfs_q1;
309: MKGFS(ai,*c);
310: }
311: }
312:
313: void divgfs(a,b,c)
314: GFS a,b;
315: GFS *c;
316: {
317: int ai;
318: GFS z;
319:
320: ntogfs(a,&z); a = z;
321: ntogfs(b,&z); b = z;
322: if ( !b )
323: error("divgfs : division by 0");
324: else if ( !a )
325: *c = 0;
326: else {
327: ai = CONT(a) - CONT(b);
328: if ( ai < 0 )
329: ai += current_gfs_q1;
330: MKGFS(ai,*c);
331: }
332: }
333:
334: void chsgngfs(a,c)
335: GFS a,*c;
336: {
337: int ai;
338: GFS z;
339:
340: ntogfs(a,&z); a = z;
341: if ( !a )
342: *c = 0;
343: else if ( current_gfs_q1&1 )
344: *c = a;
345: else {
346: /* r^((q-1)/2) = -1 */
347: ai = CONT(a)+(current_gfs_q1>>1);
348: if ( ai >= current_gfs_q1 )
349: ai -= current_gfs_q1;
350: MKGFS(ai,*c);
351: }
352: }
353:
354: void pwrgfs(a,b,c)
355: GFS a;
356: Q b;
357: GFS *c;
358: {
359: N an,tn,rn;
360: GFS t,s,z;
361:
362: ntogfs(a,&z); a = z;
363: if ( !b )
364: MKGFS(0,*c);
365: else if ( !a )
366: *c = 0;
367: else {
368: STON(CONT(a),an); muln(an,NM(b),&tn);
369: STON(current_gfs_q1,an); remn(tn,an,&rn);
370: if ( !rn )
371: MKGFS(0,*c);
372: else if ( SGN(b) > 0 )
373: MKGFS(BD(rn)[0],*c);
374: else {
375: MKGFS(0,t);
376: MKGFS(BD(rn)[0],s);
377: divgfs(t,s,c);
378: }
379: }
380: }
381:
382: int cmpgfs(a,b)
383: GFS a,b;
384: {
385: GFS z;
386:
387: ntogfs(a,&z); a = z;
388: if ( !a )
389: return !b ? 0 : -1;
390: else
391: if ( !b )
392: return 1;
393: else {
394: if ( CONT(a) > CONT(b) )
395: return 1;
396: else if ( CONT(a) < CONT(b) )
397: return -1;
398: else
399: return 0;
400: }
1.3 noro 401: }
402:
403: void randomgfs(r)
404: GFS *r;
405: {
406: unsigned int t;
407:
408: if ( !current_gfs_q1 )
409: error("addgfs : current_gfs_q is not set");
410: t = mt_genrand()%current_gfs_q;
411: if ( !t )
412: *r = 0;
413: else {
414: if ( t == current_gfs_q1 )
415: t = 0;
416: MKGFS(t,*r);
417: }
1.1 noro 418: }