| /* |
| Licensed to the Apache Software Foundation (ASF) under one |
| or more contributor license agreements. See the NOTICE file |
| distributed with this work for additional information |
| regarding copyright ownership. The ASF licenses this file |
| to you under the Apache License, Version 2.0 (the |
| "License"); you may not use this file except in compliance |
| with the License. You may obtain a copy of the License at |
| |
| http://www.apache.org/licenses/LICENSE-2.0 |
| |
| Unless required by applicable law or agreed to in writing, |
| software distributed under the License is distributed on an |
| "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY |
| KIND, either express or implied. See the License for the |
| specific language governing permissions and limitations |
| under the License. |
| */ |
| |
| /* AMCL BIG number class */ |
| |
| public class BIG |
| { |
| private long[] w = new long[ROM.NLEN]; |
| /* Constructors */ |
| public BIG() |
| { |
| for (int i = 0;i < ROM.NLEN;i++) |
| { |
| w[i] = 0; |
| } |
| } |
| |
| public BIG(int x) |
| { |
| w[0] = x; |
| for (int i = 1;i < ROM.NLEN;i++) |
| { |
| w[i] = 0; |
| } |
| } |
| |
| public BIG(BIG x) |
| { |
| for (int i = 0;i < ROM.NLEN;i++) |
| { |
| w[i] = x.w[i]; |
| } |
| } |
| |
| public BIG(DBIG x) |
| { |
| for (int i = 0;i < ROM.NLEN;i++) |
| { |
| w[i] = x.w[i]; |
| } |
| } |
| |
| public BIG(long[] x) |
| { |
| for (int i = 0;i < ROM.NLEN;i++) |
| { |
| w[i] = x[i]; |
| } |
| } |
| |
| public virtual long get(int i) |
| { |
| return w[i]; |
| } |
| |
| public virtual void set(int i, long x) |
| { |
| w[i] = x; |
| } |
| |
| public virtual void xortop(long x) |
| { |
| w[ROM.NLEN - 1] ^= x; |
| } |
| |
| public virtual void ortop(long x) |
| { |
| w[ROM.NLEN - 1] |= x; |
| } |
| |
| /* calculate Field Excess */ |
| public static long EXCESS(BIG a) |
| { |
| return ((a.w[ROM.NLEN - 1] & ROM.OMASK) >> (ROM.MODBITS % ROM.BASEBITS)); |
| } |
| |
| /* test for zero */ |
| public virtual bool iszilch() |
| { |
| for (int i = 0;i < ROM.NLEN;i++) |
| { |
| if (w[i] != 0) |
| { |
| return false; |
| } |
| } |
| return true; |
| } |
| |
| /* set to zero */ |
| public virtual void zero() |
| { |
| for (int i = 0;i < ROM.NLEN;i++) |
| { |
| w[i] = 0; |
| } |
| } |
| |
| /* set to one */ |
| public virtual void one() |
| { |
| w[0] = 1; |
| for (int i = 1;i < ROM.NLEN;i++) |
| { |
| w[i] = 0; |
| } |
| } |
| |
| /* Test for equal to one */ |
| public virtual bool isunity() |
| { |
| for (int i = 1;i < ROM.NLEN;i++) |
| { |
| if (w[i] != 0) |
| { |
| return false; |
| } |
| } |
| if (w[0] != 1) |
| { |
| return false; |
| } |
| return true; |
| } |
| |
| /* Copy from another BIG */ |
| public virtual void copy(BIG x) |
| { |
| for (int i = 0;i < ROM.NLEN;i++) |
| { |
| w[i] = x.w[i]; |
| } |
| } |
| |
| public virtual void copy(DBIG x) |
| { |
| for (int i = 0;i < ROM.NLEN;i++) |
| { |
| w[i] = x.w[i]; |
| } |
| } |
| |
| /* Conditional swap of two bigs depending on d using XOR - no branches */ |
| public virtual void cswap(BIG b, int d) |
| { |
| int i; |
| long t , c = (long)d; |
| c = ~(c - 1); |
| |
| for (i = 0;i < ROM.NLEN;i++) |
| { |
| t = c & (w[i] ^ b.w[i]); |
| w[i] ^= t; |
| b.w[i] ^= t; |
| } |
| } |
| |
| public virtual void cmove(BIG g, int d) |
| { |
| int i; |
| long b = -d; |
| |
| for (i = 0;i < ROM.NLEN;i++) |
| { |
| w[i] ^= (w[i] ^ g.w[i]) & b; |
| } |
| } |
| |
| |
| /* normalise BIG - force all digits < 2^BASEBITS */ |
| public virtual long norm() |
| { |
| long d , carry = 0; |
| for (int i = 0;i < ROM.NLEN - 1;i++) |
| { |
| d = w[i] + carry; |
| w[i] = d & ROM.MASK; |
| carry = d >> ROM.BASEBITS; |
| } |
| w[ROM.NLEN - 1] = (w[ROM.NLEN - 1] + carry); |
| return (w[ROM.NLEN - 1] >> ((8 * ROM.MODBYTES) % ROM.BASEBITS)); |
| } |
| |
| /* Shift right by less than a word */ |
| public virtual long fshr(int k) |
| { |
| long r = w[0] & (((long)1 << k) - 1); // shifted out part |
| for (int i = 0;i < ROM.NLEN - 1;i++) |
| { |
| w[i] = (w[i] >> k) | ((w[i + 1] << (ROM.BASEBITS - k)) & ROM.MASK); |
| } |
| w[ROM.NLEN - 1] = w[ROM.NLEN - 1] >> k; |
| return r; |
| } |
| |
| /* general shift right */ |
| public virtual void shr(int k) |
| { |
| int n = k % ROM.BASEBITS; |
| int m = k / ROM.BASEBITS; |
| for (int i = 0;i < ROM.NLEN - m - 1;i++) |
| { |
| w[i] = (w[m + i] >> n) | ((w[m + i + 1] << (ROM.BASEBITS - n)) & ROM.MASK); |
| } |
| w[ROM.NLEN - m - 1] = w[ROM.NLEN - 1] >> n; |
| for (int i = ROM.NLEN - m;i < ROM.NLEN;i++) |
| { |
| w[i] = 0; |
| } |
| } |
| |
| /* Shift right by less than a word */ |
| public virtual long fshl(int k) |
| { |
| w[ROM.NLEN - 1] = ((w[ROM.NLEN - 1] << k)) | (w[ROM.NLEN - 2]>>(ROM.BASEBITS - k)); |
| for (int i = ROM.NLEN - 2;i > 0;i--) |
| { |
| w[i] = ((w[i] << k) & ROM.MASK) | (w[i - 1]>>(ROM.BASEBITS - k)); |
| } |
| w[0] = (w[0] << k) & ROM.MASK; |
| return (w[ROM.NLEN - 1] >> ((8 * ROM.MODBYTES) % ROM.BASEBITS)); // return excess - only used in ff.c |
| } |
| |
| /* general shift left */ |
| public virtual void shl(int k) |
| { |
| int n = k % ROM.BASEBITS; |
| int m = k / ROM.BASEBITS; |
| |
| w[ROM.NLEN - 1] = ((w[ROM.NLEN - 1 - m] << n)) | (w[ROM.NLEN - m - 2]>>(ROM.BASEBITS - n)); |
| for (int i = ROM.NLEN - 2;i > m;i--) |
| { |
| w[i] = ((w[i - m] << n) & ROM.MASK) | (w[i - m - 1]>>(ROM.BASEBITS - n)); |
| } |
| w[m] = (w[0] << n) & ROM.MASK; |
| for (int i = 0;i < m;i++) |
| { |
| w[i] = 0; |
| } |
| } |
| |
| /* return number of bits */ |
| public virtual int nbits() |
| { |
| int bts , k = ROM.NLEN - 1; |
| long c; |
| norm(); |
| while (k >= 0 && w[k] == 0) |
| { |
| k--; |
| } |
| if (k < 0) |
| { |
| return 0; |
| } |
| bts = ROM.BASEBITS * k; |
| c = w[k]; |
| while (c != 0) |
| { |
| c /= 2; |
| bts++; |
| } |
| return bts; |
| } |
| |
| public virtual string toRawString() |
| { |
| BIG b = new BIG(this); |
| string s = "("; |
| for (int i = 0;i < ROM.NLEN - 1;i++) |
| { |
| s += b.w[i].ToString("x"); |
| s += ","; |
| } |
| s += b.w[ROM.NLEN - 1].ToString("x"); |
| s += ")"; |
| return s; |
| } |
| |
| /* Convert to Hex String */ |
| public override string ToString() |
| { |
| BIG b; |
| string s = ""; |
| int len = nbits(); |
| |
| if (len % 4 == 0) |
| { |
| len /= 4; |
| } |
| else |
| { |
| len /= 4; |
| len++; |
| } |
| if (len < ROM.MODBYTES * 2) |
| { |
| len = ROM.MODBYTES * 2; |
| } |
| |
| for (int i = len - 1;i >= 0;i--) |
| { |
| b = new BIG(this); |
| b.shr(i * 4); |
| s += (b.w[0] & 15).ToString("x"); |
| } |
| return s; |
| } |
| |
| /* return this+x */ |
| public virtual BIG plus(BIG x) |
| { |
| BIG s = new BIG(0); |
| for (int i = 0;i < ROM.NLEN;i++) |
| { |
| s.w[i] = w[i] + x.w[i]; |
| } |
| return s; |
| } |
| |
| /* this+=x */ |
| public virtual void add(BIG x) |
| { |
| for (int i = 0;i < ROM.NLEN;i++) |
| { |
| w[i] += x.w[i]; |
| } |
| } |
| |
| /* this+=x, where x is int */ |
| public virtual void inc(int x) |
| { |
| norm(); |
| w[0] += x; |
| } |
| |
| /* return this.x */ |
| public virtual BIG minus(BIG x) |
| { |
| BIG d = new BIG(0); |
| for (int i = 0;i < ROM.NLEN;i++) |
| { |
| d.w[i] = w[i] - x.w[i]; |
| } |
| return d; |
| } |
| |
| /* this-=x */ |
| public virtual void sub(BIG x) |
| { |
| for (int i = 0;i < ROM.NLEN;i++) |
| { |
| w[i] -= x.w[i]; |
| } |
| } |
| |
| /* reverse subtract this=x-this */ |
| public virtual void rsub(BIG x) |
| { |
| for (int i = 0;i < ROM.NLEN;i++) |
| { |
| w[i] = x.w[i] - w[i]; |
| } |
| } |
| |
| /* this-=x where x is int */ |
| public virtual void dec(int x) |
| { |
| norm(); |
| w[0] -= (long)x; |
| } |
| |
| /* this*=x, where x is small int<NEXCESS */ |
| public virtual void imul(int c) |
| { |
| for (int i = 0;i < ROM.NLEN;i++) |
| { |
| w[i] *= c; |
| } |
| } |
| |
| /* convert this BIG to byte array */ |
| public virtual void tobytearray(sbyte[] b, int n) |
| { |
| norm(); |
| BIG c = new BIG(this); |
| |
| for (int i = ROM.MODBYTES - 1;i >= 0;i--) |
| { |
| b[i + n] = (sbyte)c.w[0]; |
| c.fshr(8); |
| } |
| } |
| |
| /* convert from byte array to BIG */ |
| public static BIG frombytearray(sbyte[] b, int n) |
| { |
| BIG m = new BIG(0); |
| |
| for (int i = 0;i < ROM.MODBYTES;i++) |
| { |
| m.fshl(8); |
| m.w[0] += (int)b[i + n] & 0xff; |
| //m.inc((int)b[i]&0xff); |
| } |
| return m; |
| } |
| |
| public virtual void toBytes(sbyte[] b) |
| { |
| tobytearray(b,0); |
| } |
| |
| public static BIG fromBytes(sbyte[] b) |
| { |
| return frombytearray(b,0); |
| } |
| |
| |
| /* set this[i]+=x*y+c, and return high part */ |
| |
| public virtual long muladd(long a, long b, long c, int i) |
| { |
| long x0, x1, y0, y1; |
| x0 = a & ROM.HMASK; |
| x1 = (a >> ROM.HBITS); |
| y0 = b & ROM.HMASK; |
| y1 = (b >> ROM.HBITS); |
| long bot = x0 * y0; |
| long top = x1 * y1; |
| long mid = x0 * y1 + x1 * y0; |
| x0 = mid & ROM.HMASK; |
| x1 = (mid >> ROM.HBITS); |
| bot += x0 << ROM.HBITS; |
| bot += c; |
| bot += w[i]; |
| top += x1; |
| long carry = bot >> ROM.BASEBITS; |
| bot &= ROM.MASK; |
| top += carry; |
| w[i] = bot; |
| return top; |
| } |
| |
| /* this*=x, where x is >NEXCESS */ |
| public virtual long pmul(int c) |
| { |
| long ak , carry = 0; |
| norm(); |
| for (int i = 0;i < ROM.NLEN;i++) |
| { |
| ak = w[i]; |
| w[i] = 0; |
| carry = muladd(ak,(long)c,carry,i); |
| } |
| return carry; |
| } |
| |
| /* this*=c and catch overflow in DBIG */ |
| public virtual DBIG pxmul(int c) |
| { |
| DBIG m = new DBIG(0); |
| long carry = 0; |
| for (int j = 0;j < ROM.NLEN;j++) |
| { |
| carry = m.muladd(w[j],(long)c,carry,j); |
| } |
| m.w[ROM.NLEN] = carry; |
| return m; |
| } |
| |
| /* divide by 3 */ |
| public virtual int div3() |
| { |
| long ak , @base , carry = 0; |
| norm(); |
| @base = ((long)1 << ROM.BASEBITS); |
| for (int i = ROM.NLEN - 1;i >= 0;i--) |
| { |
| ak = (carry * @base + w[i]); |
| w[i] = ak / 3; |
| carry = ak % 3; |
| } |
| return (int)carry; |
| } |
| |
| /* return a*b where result fits in a BIG */ |
| public static BIG smul(BIG a, BIG b) |
| { |
| long carry; |
| BIG c = new BIG(0); |
| for (int i = 0;i < ROM.NLEN;i++) |
| { |
| carry = 0; |
| for (int j = 0;j < ROM.NLEN;j++) |
| { |
| if (i + j < ROM.NLEN) |
| { |
| carry = c.muladd(a.w[i],b.w[j],carry,i + j); |
| } |
| } |
| } |
| return c; |
| } |
| |
| /* Compare a and b, return 0 if a==b, -1 if a<b, +1 if a>b. Inputs must be normalised */ |
| public static int comp(BIG a, BIG b) |
| { |
| for (int i = ROM.NLEN - 1;i >= 0;i--) |
| { |
| if (a.w[i] == b.w[i]) |
| { |
| continue; |
| } |
| if (a.w[i] > b.w[i]) |
| { |
| return 1; |
| } |
| else |
| { |
| return -1; |
| } |
| } |
| return 0; |
| } |
| |
| /* set x = x mod 2^m */ |
| public virtual void mod2m(int m) |
| { |
| int i, wd, bt; |
| long msk; |
| |
| wd = m / ROM.BASEBITS; |
| bt = m % ROM.BASEBITS; |
| msk = ((long)1 << bt) - 1; |
| w[wd] &= msk; |
| for (i = wd + 1;i < ROM.NLEN;i++) |
| { |
| w[i] = 0; |
| } |
| } |
| |
| /* Arazi and Qi inversion mod 256 */ |
| public static int invmod256(int a) |
| { |
| int U, t1, t2, b, c; |
| t1 = 0; |
| c = (a >> 1) & 1; |
| t1 += c; |
| t1 &= 1; |
| t1 = 2 - t1; |
| t1 <<= 1; |
| U = t1 + 1; |
| |
| // i=2 |
| b = a & 3; |
| t1 = U * b; |
| t1 >>= 2; |
| c = (a >> 2) & 3; |
| t2 = (U * c) & 3; |
| t1 += t2; |
| t1 *= U; |
| t1 &= 3; |
| t1 = 4 - t1; |
| t1 <<= 2; |
| U += t1; |
| |
| // i=4 |
| b = a & 15; |
| t1 = U * b; |
| t1 >>= 4; |
| c = (a >> 4) & 15; |
| t2 = (U * c) & 15; |
| t1 += t2; |
| t1 *= U; |
| t1 &= 15; |
| t1 = 16 - t1; |
| t1 <<= 4; |
| U += t1; |
| |
| return U; |
| } |
| |
| /* a=1/a mod 2^256. This is very fast! */ |
| public virtual void invmod2m() |
| { |
| int i; |
| BIG U = new BIG(0); |
| BIG b = new BIG(0); |
| BIG c = new BIG(0); |
| |
| U.inc(invmod256(lastbits(8))); |
| |
| for (i = 8;i < 256;i <<= 1) |
| { |
| b.copy(this); |
| b.mod2m(i); |
| BIG t1 = BIG.smul(U,b); |
| t1.shr(i); |
| c.copy(this); |
| c.shr(i); |
| c.mod2m(i); |
| |
| BIG t2 = BIG.smul(U,c); |
| t2.mod2m(i); |
| t1.add(t2); |
| b = BIG.smul(t1,U); |
| t1.copy(b); |
| t1.mod2m(i); |
| |
| t2.one(); |
| t2.shl(i); |
| t1.rsub(t2); |
| t1.norm(); |
| t1.shl(i); |
| U.add(t1); |
| } |
| this.copy(U); |
| } |
| |
| /* reduce this mod m */ |
| public virtual void mod(BIG m) |
| { |
| int k = 0; |
| |
| norm(); |
| if (comp(this,m) < 0) |
| { |
| return; |
| } |
| do |
| { |
| m.fshl(1); |
| k++; |
| } while (comp(this,m) >= 0); |
| |
| while (k > 0) |
| { |
| m.fshr(1); |
| if (comp(this,m) >= 0) |
| { |
| sub(m); |
| norm(); |
| } |
| k--; |
| } |
| } |
| |
| /* divide this by m */ |
| public virtual void div(BIG m) |
| { |
| int k = 0; |
| norm(); |
| BIG e = new BIG(1); |
| BIG b = new BIG(this); |
| zero(); |
| |
| while (comp(b,m) >= 0) |
| { |
| e.fshl(1); |
| m.fshl(1); |
| k++; |
| } |
| |
| while (k > 0) |
| { |
| m.fshr(1); |
| e.fshr(1); |
| if (comp(b,m) >= 0) |
| { |
| add(e); |
| norm(); |
| b.sub(m); |
| b.norm(); |
| } |
| k--; |
| } |
| } |
| |
| /* return parity */ |
| public virtual int parity() |
| { |
| return (int)(w[0] % 2); |
| } |
| |
| /* return n-th bit */ |
| public virtual int bit(int n) |
| { |
| if ((w[n / ROM.BASEBITS] & ((long)1 << (n % ROM.BASEBITS)))>0) |
| { |
| return 1; |
| } |
| else |
| { |
| return 0; |
| } |
| } |
| |
| /* return n last bits */ |
| public virtual int lastbits(int n) |
| { |
| int msk = (1 << n) - 1; |
| norm(); |
| return ((int)w[0]) & msk; |
| } |
| |
| /* get 8*MODBYTES size random number */ |
| public static BIG random(RAND rng) |
| { |
| BIG m = new BIG(0); |
| int i , b , j = 0, r = 0; |
| |
| /* generate random BIG */ |
| for (i = 0;i < 8 * ROM.MODBYTES;i++) |
| { |
| if (j == 0) |
| { |
| r = rng.Byte; |
| } |
| else |
| { |
| r >>= 1; |
| } |
| |
| b = r & 1; |
| m.shl(1); |
| m.w[0] += b; // m.inc(b); |
| j++; |
| j &= 7; |
| } |
| return m; |
| } |
| |
| /* Create random BIG in portable way, one bit at a time */ |
| public static BIG randomnum(BIG q, RAND rng) |
| { |
| DBIG d = new DBIG(0); |
| int i , b , j = 0, r = 0; |
| for (i = 0;i < 2 * ROM.MODBITS;i++) |
| { |
| if (j == 0) |
| { |
| r = rng.Byte; |
| } |
| else |
| { |
| r >>= 1; |
| } |
| |
| b = r & 1; |
| d.shl(1); |
| d.w[0] += b; // m.inc(b); |
| j++; |
| j &= 7; |
| } |
| BIG m = d.mod(q); |
| return m; |
| } |
| |
| /* return NAF value as +/- 1, 3 or 5. x and x3 should be normed. |
| nbs is number of bits processed, and nzs is number of trailing 0s detected */ |
| public static int[] nafbits(BIG x, BIG x3, int i) |
| { |
| int[] n = new int[3]; |
| int nb = x3.bit(i) - x.bit(i); |
| int j; |
| n[1] = 1; |
| n[0] = 0; |
| if (nb == 0) |
| { |
| n[0] = 0; |
| return n; |
| } |
| if (i == 0) |
| { |
| n[0] = nb; |
| return n; |
| } |
| if (nb > 0) |
| { |
| n[0] = 1; |
| } |
| else |
| { |
| n[0] = (-1); |
| } |
| |
| for (j = i - 1;j > 0;j--) |
| { |
| n[1]++; |
| n[0] *= 2; |
| nb = x3.bit(j) - x.bit(j); |
| if (nb > 0) |
| { |
| n[0] += 1; |
| } |
| if (nb < 0) |
| { |
| n[0] -= 1; |
| } |
| if (n[0] > 5 || n[0] < -5) |
| { |
| break; |
| } |
| } |
| |
| if (n[0] % 2 != 0 && j != 0) |
| { // backtrack |
| if (nb > 0) |
| { |
| n[0] = (n[0] - 1) / 2; |
| } |
| if (nb < 0) |
| { |
| n[0] = (n[0] + 1) / 2; |
| } |
| n[1]--; |
| } |
| while (n[0] % 2 == 0) |
| { // remove trailing zeros |
| n[0] /= 2; |
| n[2]++; |
| n[1]--; |
| } |
| return n; |
| } |
| |
| /* return a*b as DBIG */ |
| public static DBIG mul(BIG a, BIG b) |
| { |
| DBIG c = new DBIG(0); |
| long carry; |
| a.norm(); |
| b.norm(); |
| |
| for (int i = 0;i < ROM.NLEN;i++) |
| { |
| carry = 0; |
| for (int j = 0;j < ROM.NLEN;j++) |
| { |
| carry = c.muladd(a.w[i],b.w[j],carry,i + j); |
| } |
| c.w[ROM.NLEN + i] = carry; |
| } |
| |
| return c; |
| } |
| |
| /* return a^2 as DBIG */ |
| public static DBIG sqr(BIG a) |
| { |
| DBIG c = new DBIG(0); |
| long carry; |
| a.norm(); |
| for (int i = 0;i < ROM.NLEN;i++) |
| { |
| carry = 0; |
| for (int j = i + 1;j < ROM.NLEN;j++) |
| { |
| carry = c.muladd(2 * a.w[i],a.w[j],carry,i + j); |
| } |
| c.w[ROM.NLEN + i] = carry; |
| } |
| |
| for (int i = 0;i < ROM.NLEN;i++) |
| { |
| c.w[2 * i + 1] += c.muladd(a.w[i],a.w[i],0,2 * i); |
| } |
| |
| c.norm(); |
| return c; |
| } |
| |
| /* reduce a DBIG to a BIG using the appropriate form of the modulus */ |
| public static BIG mod(DBIG d) |
| { |
| BIG b; |
| if (ROM.MODTYPE == ROM.PSEUDO_MERSENNE) |
| { |
| long v, tw; |
| BIG t = d.Split(ROM.MODBITS); |
| b = new BIG(d); |
| unchecked |
| { |
| v = t.pmul((int)ROM.MConst); |
| } |
| tw = t.w[ROM.NLEN - 1]; |
| t.w[ROM.NLEN - 1] &= ROM.TMASK; |
| t.w[0] += (ROM.MConst * ((tw >> ROM.TBITS) + (v << (ROM.BASEBITS - ROM.TBITS)))); |
| |
| b.add(t); |
| b.norm(); |
| } |
| if (ROM.MODTYPE == ROM.MONTGOMERY_FRIENDLY) |
| { |
| for (int i = 0;i < ROM.NLEN;i++) |
| { |
| d.w[ROM.NLEN + i] += d.muladd(d.w[i],ROM.MConst - 1,d.w[i],ROM.NLEN + i - 1); |
| } |
| |
| b = new BIG(0); |
| |
| for (int i = 0;i < ROM.NLEN;i++) |
| { |
| b.w[i] = d.w[ROM.NLEN + i]; |
| } |
| b.norm(); |
| } |
| |
| if (ROM.MODTYPE == ROM.NOT_SPECIAL) |
| { |
| BIG md = new BIG(ROM.Modulus); |
| long m, carry; |
| for (int i = 0;i < ROM.NLEN;i++) |
| { |
| if (ROM.MConst == -1) |
| { |
| m = (-d.w[i]) & ROM.MASK; |
| } |
| else |
| { |
| if (ROM.MConst == 1) |
| { |
| m = d.w[i]; |
| } |
| else |
| { |
| m = (ROM.MConst * d.w[i]) & ROM.MASK; |
| } |
| } |
| |
| carry = 0; |
| for (int j = 0;j < ROM.NLEN;j++) |
| { |
| carry = d.muladd(m,md.w[j],carry,i + j); |
| } |
| d.w[ROM.NLEN + i] += carry; |
| } |
| |
| b = new BIG(0); |
| for (int i = 0;i < ROM.NLEN;i++) |
| { |
| b.w[i] = d.w[ROM.NLEN + i]; |
| } |
| b.norm(); |
| } |
| |
| return b; |
| } |
| |
| /* return a*b mod m */ |
| public static BIG modmul(BIG a, BIG b, BIG m) |
| { |
| a.mod(m); |
| b.mod(m); |
| DBIG d = mul(a,b); |
| return d.mod(m); |
| } |
| |
| /* return a^2 mod m */ |
| public static BIG modsqr(BIG a, BIG m) |
| { |
| a.mod(m); |
| DBIG d = sqr(a); |
| return d.mod(m); |
| } |
| |
| /* return -a mod m */ |
| public static BIG modneg(BIG a, BIG m) |
| { |
| a.mod(m); |
| return m.minus(a); |
| } |
| |
| /* return this^e mod m */ |
| public virtual BIG powmod(BIG e, BIG m) |
| { |
| int bt; |
| norm(); |
| e.norm(); |
| BIG a = new BIG(1); |
| BIG z = new BIG(e); |
| BIG s = new BIG(this); |
| while (true) |
| { |
| bt = z.parity(); |
| z.fshr(1); |
| if (bt == 1) |
| { |
| a = modmul(a,s,m); |
| } |
| if (z.iszilch()) |
| { |
| break; |
| } |
| s = modsqr(s,m); |
| } |
| return a; |
| } |
| |
| /* Jacobi Symbol (this/p). Returns 0, 1 or -1 */ |
| public virtual int jacobi(BIG p) |
| { |
| int n8 , k , m = 0; |
| BIG t = new BIG(0); |
| BIG x = new BIG(0); |
| BIG n = new BIG(0); |
| BIG zilch = new BIG(0); |
| BIG one = new BIG(1); |
| if (p.parity() == 0 || comp(this,zilch) == 0 || comp(p,one) <= 0) |
| { |
| return 0; |
| } |
| norm(); |
| x.copy(this); |
| n.copy(p); |
| x.mod(p); |
| |
| while (comp(n,one) > 0) |
| { |
| if (comp(x,zilch) == 0) |
| { |
| return 0; |
| } |
| n8 = n.lastbits(3); |
| k = 0; |
| while (x.parity() == 0) |
| { |
| k++; |
| x.shr(1); |
| } |
| if (k % 2 == 1) |
| { |
| m += (n8 * n8 - 1) / 8; |
| } |
| m += (n8 - 1) * (x.lastbits(2) - 1) / 4; |
| t.copy(n); |
| t.mod(x); |
| n.copy(x); |
| x.copy(t); |
| m %= 2; |
| |
| } |
| if (m == 0) |
| { |
| return 1; |
| } |
| else |
| { |
| return -1; |
| } |
| } |
| |
| /* this=1/this mod p. Binary method */ |
| public virtual void invmodp(BIG p) |
| { |
| mod(p); |
| BIG u = new BIG(this); |
| |
| BIG v = new BIG(p); |
| BIG x1 = new BIG(1); |
| BIG x2 = new BIG(0); |
| BIG t = new BIG(0); |
| BIG one = new BIG(1); |
| while (comp(u,one) != 0 && comp(v,one) != 0) |
| { |
| while (u.parity() == 0) |
| { |
| u.shr(1); |
| if (x1.parity() != 0) |
| { |
| x1.add(p); |
| x1.norm(); |
| } |
| x1.shr(1); |
| } |
| while (v.parity() == 0) |
| { |
| v.shr(1); |
| if (x2.parity() != 0) |
| { |
| x2.add(p); |
| x2.norm(); |
| } |
| x2.shr(1); |
| } |
| if (comp(u,v) >= 0) |
| { |
| u.sub(v); |
| u.norm(); |
| if (comp(x1,x2) >= 0) |
| { |
| x1.sub(x2); |
| } |
| else |
| { |
| t.copy(p); |
| t.sub(x2); |
| x1.add(t); |
| } |
| x1.norm(); |
| } |
| else |
| { |
| v.sub(u); |
| v.norm(); |
| if (comp(x2,x1) >= 0) |
| { |
| x2.sub(x1); |
| } |
| else |
| { |
| t.copy(p); |
| t.sub(x1); |
| x2.add(t); |
| } |
| x2.norm(); |
| } |
| } |
| if (comp(u,one) == 0) |
| { |
| copy(x1); |
| } |
| else |
| { |
| copy(x2); |
| } |
| } |
| } |