Annotation of OpenXM_contrib2/asir2000/engine/gfs.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 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: *
! 48: * $OpenXM$
! 49: */
! 50: #include "ca.h"
! 51:
! 52: /* q = p^n */
! 53:
! 54: int current_gfs_ext;
! 55: int current_gfs_q;
! 56: int current_gfs_q1;
! 57: int *current_gfs_plus1;
! 58: int *current_gfs_ntoi;
! 59: int *current_gfs_iton;
! 60:
! 61: void chsgngfs();
! 62:
! 63: /*
! 64: * current_gfs_iton[i] = r^i mod p (i=0,...,p-2)
! 65: * current_gfs_iton[p-1] = 0
! 66: */
! 67:
! 68: void setmod_sf(p,n)
! 69: int p,n;
! 70: {
! 71: int r,i,p1;
! 72:
! 73: if ( n > 1 )
! 74: error("setup_gfs : not implemented yet");
! 75: else {
! 76: r = generate_primitive_root_p(p);
! 77: current_gfs_q = p;
! 78: current_gfs_ext = 1;
! 79: current_gfs_q1 = p1 = p-1;
! 80:
! 81: current_gfs_iton = (int *)MALLOC(p1*sizeof(int));
! 82: current_gfs_iton[0] = 1;
! 83: for ( i = 1; i < p1; i++ )
! 84: current_gfs_iton[i] = (current_gfs_iton[i-1]*r)%p;
! 85:
! 86: current_gfs_ntoi = (int *)MALLOC(p*sizeof(int));
! 87: current_gfs_ntoi[0] = -1;
! 88: for ( i = 0; i < p1; i++ )
! 89: current_gfs_ntoi[current_gfs_iton[i]] = i;
! 90:
! 91: current_gfs_plus1 = (int *)MALLOC(p*sizeof(int));
! 92: for ( i = 0; i < p1; i++ )
! 93: current_gfs_plus1[i]
! 94: = current_gfs_ntoi[(current_gfs_iton[i]+1)%p];
! 95: }
! 96: }
! 97:
! 98: int generate_primitive_root_p(p)
! 99: int p;
! 100: {
! 101: int r,rj,j;
! 102:
! 103: for ( r = 2; r < p; r++ ) {
! 104: rj = r;
! 105: for ( j = 1; j < p-1 && rj != 1; j++ )
! 106: rj = (rj*r) % p;
! 107: if ( j == p-1 )
! 108: return r;
! 109: }
! 110: }
! 111:
! 112: void mqtogfs(a,c)
! 113: MQ a;
! 114: GFS *c;
! 115: {
! 116: if ( !a )
! 117: *c = 0;
! 118: else {
! 119: MKGFS(current_gfs_ntoi[CONT(a)],*c);
! 120: }
! 121: }
! 122:
! 123: void gfstomq(a,c)
! 124: GFS a;
! 125: MQ *c;
! 126: {
! 127: if ( !a )
! 128: *c = 0;
! 129: else {
! 130: UTOMQ(current_gfs_iton[CONT(a)],*c);
! 131: }
! 132: }
! 133:
! 134: void ntogfs(a,b)
! 135: Obj a;
! 136: GFS *b;
! 137: {
! 138: P t;
! 139:
! 140: if ( !current_gfs_q1 )
! 141: error("addgfs : current_gfs_q is not set");
! 142: if ( !a || (OID(a)==O_N && NID(a) == N_GFS) )
! 143: *b = (GFS)a;
! 144: else if ( OID(a) == O_N && NID(a) == N_M )
! 145: mqtogfs(a,b);
! 146: else if ( OID(a) == O_N && NID(a) == N_Q ) {
! 147: ptomp(current_gfs_q,(P)a,&t); mqtogfs(t,b);
! 148: } else
! 149: error("ntogfs : invalid argument");
! 150: }
! 151:
! 152: void addgfs(a,b,c)
! 153: GFS a,b;
! 154: GFS *c;
! 155: {
! 156: int ai,bi,ci;
! 157: GFS z;
! 158:
! 159: ntogfs(a,&z); a = z;
! 160: ntogfs(b,&z); b = z;
! 161: if ( !a )
! 162: *c = b;
! 163: else if ( !b )
! 164: *c = a;
! 165: else {
! 166: ai = CONT(a); bi = CONT(b);
! 167: if ( ai > bi ) {
! 168: /* tab[ai]+tab[bi] = tab[bi](tab[ai-bi]+1) */
! 169: ci = current_gfs_plus1[ai-bi];
! 170: if ( ci < 0 )
! 171: *c = 0;
! 172: else {
! 173: ci += bi;
! 174: if ( ci >= current_gfs_q1 )
! 175: ci -= current_gfs_q1;
! 176: MKGFS(ci,*c);
! 177: }
! 178: } else {
! 179: /* tab[ai]+tab[bi] = tab[ai](tab[bi-ai]+1) */
! 180: ci = current_gfs_plus1[bi-ai];
! 181: if ( ci < 0 )
! 182: *c = 0;
! 183: else {
! 184: ci += ai;
! 185: if ( ci >= current_gfs_q1 )
! 186: ci -= current_gfs_q1;
! 187: MKGFS(ci,*c);
! 188: }
! 189: }
! 190: }
! 191: }
! 192:
! 193: void subgfs(a,b,c)
! 194: GFS a,b;
! 195: GFS *c;
! 196: {
! 197: GFS t,z;
! 198:
! 199: ntogfs(a,&z); a = z;
! 200: ntogfs(b,&z); b = z;
! 201: if ( !b )
! 202: *c = a;
! 203: else {
! 204: chsgngfs(b,&t);
! 205: addgfs(a,t,c);
! 206: }
! 207: }
! 208:
! 209: void mulgfs(a,b,c)
! 210: GFS a,b;
! 211: GFS *c;
! 212: {
! 213: int ai;
! 214: GFS z;
! 215:
! 216: ntogfs(a,&z); a = z;
! 217: ntogfs(b,&z); b = z;
! 218: if ( !a || !b )
! 219: *c = 0;
! 220: else {
! 221: ai = CONT(a) + CONT(b);
! 222: if ( ai >= current_gfs_q1 )
! 223: ai -= current_gfs_q1;
! 224: MKGFS(ai,*c);
! 225: }
! 226: }
! 227:
! 228: void divgfs(a,b,c)
! 229: GFS a,b;
! 230: GFS *c;
! 231: {
! 232: int ai;
! 233: GFS z;
! 234:
! 235: ntogfs(a,&z); a = z;
! 236: ntogfs(b,&z); b = z;
! 237: if ( !b )
! 238: error("divgfs : division by 0");
! 239: else if ( !a )
! 240: *c = 0;
! 241: else {
! 242: ai = CONT(a) - CONT(b);
! 243: if ( ai < 0 )
! 244: ai += current_gfs_q1;
! 245: MKGFS(ai,*c);
! 246: }
! 247: }
! 248:
! 249: void chsgngfs(a,c)
! 250: GFS a,*c;
! 251: {
! 252: int ai;
! 253: GFS z;
! 254:
! 255: ntogfs(a,&z); a = z;
! 256: if ( !a )
! 257: *c = 0;
! 258: else if ( current_gfs_q1&1 )
! 259: *c = a;
! 260: else {
! 261: /* r^((q-1)/2) = -1 */
! 262: ai = CONT(a)+(current_gfs_q1>>1);
! 263: if ( ai >= current_gfs_q1 )
! 264: ai -= current_gfs_q1;
! 265: MKGFS(ai,*c);
! 266: }
! 267: }
! 268:
! 269: void pwrgfs(a,b,c)
! 270: GFS a;
! 271: Q b;
! 272: GFS *c;
! 273: {
! 274: N an,tn,rn;
! 275: GFS t,s,z;
! 276:
! 277: ntogfs(a,&z); a = z;
! 278: if ( !b )
! 279: MKGFS(0,*c);
! 280: else if ( !a )
! 281: *c = 0;
! 282: else {
! 283: STON(CONT(a),an); muln(an,NM(b),&tn);
! 284: STON(current_gfs_q1,an); remn(tn,an,&rn);
! 285: if ( !rn )
! 286: MKGFS(0,*c);
! 287: else if ( SGN(b) > 0 )
! 288: MKGFS(BD(rn)[0],*c);
! 289: else {
! 290: MKGFS(0,t);
! 291: MKGFS(BD(rn)[0],s);
! 292: divgfs(t,s,c);
! 293: }
! 294: }
! 295: }
! 296:
! 297: int cmpgfs(a,b)
! 298: GFS a,b;
! 299: {
! 300: GFS z;
! 301:
! 302: ntogfs(a,&z); a = z;
! 303: if ( !a )
! 304: return !b ? 0 : -1;
! 305: else
! 306: if ( !b )
! 307: return 1;
! 308: else {
! 309: if ( CONT(a) > CONT(b) )
! 310: return 1;
! 311: else if ( CONT(a) < CONT(b) )
! 312: return -1;
! 313: else
! 314: return 0;
! 315: }
! 316: }
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[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