| /* |
| 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. |
| */ |
| |
| /* Finite Field arithmetic */ |
| /* AMCL mod p functions */ |
| |
| public final class FP { |
| private final BIG x; |
| private static BIG p=new BIG(ROM.Modulus); |
| |
| /* Constructors */ |
| public FP(int a) |
| { |
| x=new BIG(a); |
| nres(); |
| } |
| |
| public FP() |
| { |
| x=new BIG(0); |
| } |
| |
| public FP(BIG a) |
| { |
| x=new BIG(a); |
| nres(); |
| } |
| |
| public FP(FP a) |
| { |
| x=new BIG(a.x); |
| } |
| |
| /* convert to string */ |
| public String toString() |
| { |
| String s=redc().toString(); |
| return s; |
| } |
| |
| public String toRawString() |
| { |
| String s=x.toRawString(); |
| return s; |
| } |
| |
| /* convert to Montgomery n-residue form */ |
| public void nres() |
| { |
| if (ROM.MODTYPE!=ROM.PSEUDO_MERSENNE && ROM.MODTYPE!=ROM.GENERALISED_MERSENNE) |
| { |
| DBIG d=new DBIG(x); |
| d.shl(ROM.NLEN*ROM.BASEBITS); |
| x.copy(d.mod(p)); |
| } |
| } |
| |
| /* convert back to regular form */ |
| public BIG redc() |
| { |
| if (ROM.MODTYPE!=ROM.PSEUDO_MERSENNE && ROM.MODTYPE!=ROM.GENERALISED_MERSENNE) |
| { |
| DBIG d=new DBIG(x); |
| return BIG.mod(d); |
| } |
| else |
| { |
| BIG r=new BIG(x); |
| return r; |
| } |
| } |
| |
| /* test this=0? */ |
| public boolean iszilch() { |
| reduce(); |
| return x.iszilch(); |
| } |
| |
| /* copy from FP b */ |
| public void copy(FP b) |
| { |
| x.copy(b.x); |
| } |
| |
| /* set this=0 */ |
| public void zero() |
| { |
| x.zero(); |
| } |
| |
| /* set this=1 */ |
| public void one() |
| { |
| x.one(); nres(); |
| } |
| |
| /* normalise this */ |
| public void norm() |
| { |
| x.norm(); |
| } |
| |
| /* swap FPs depending on d */ |
| public void cswap(FP b,int d) |
| { |
| x.cswap(b.x,d); |
| } |
| |
| /* copy FPs depending on d */ |
| public void cmove(FP b,int d) |
| { |
| x.cmove(b.x,d); |
| } |
| |
| /* this*=b mod Modulus */ |
| public void mul(FP b) |
| { |
| norm(); |
| b.norm(); |
| |
| if (BIG.pexceed(x,b.x)) reduce(); |
| |
| DBIG d=BIG.mul(x,b.x); |
| x.copy(BIG.mod(d)); |
| } |
| |
| /* this*=c mod Modulus, where c is a small int */ |
| public void imul(int c) |
| { |
| norm(); |
| boolean s=false; |
| if (c<0) |
| { |
| c=-c; |
| s=true; |
| } |
| if (c<ROM.NEXCESS && ((BIG.EXCESS(x)+1)*(c+1)+1)<ROM.FEXCESS) |
| { |
| x.imul(c); |
| } |
| else |
| { |
| if (((BIG.EXCESS(x)+1)*(c+1)+1)<ROM.FEXCESS) x.pmul(c); |
| else |
| { |
| DBIG d=x.pxmul(c); |
| x.copy(d.mod(p)); |
| } |
| } |
| if (s) neg(); |
| norm(); |
| } |
| |
| /* this*=this mod Modulus */ |
| public void sqr() |
| { |
| DBIG d; |
| norm(); |
| |
| if (BIG.sexceed(x)) reduce(); |
| |
| d=BIG.sqr(x); |
| x.copy(BIG.mod(d)); |
| } |
| |
| /* this+=b */ |
| public void add(FP b) { |
| x.add(b.x); |
| if (BIG.EXCESS(x)+2>=ROM.FEXCESS) reduce(); |
| } |
| |
| // https://graphics.stanford.edu/~seander/bithacks.html |
| // constant time log to base 2 (or number of bits in) |
| |
| private static int logb2(int v) |
| { |
| int r; |
| v |= v >>> 1; |
| v |= v >>> 2; |
| v |= v >>> 4; |
| v |= v >>> 8; |
| v |= v >>> 16; |
| |
| v = v - ((v >>> 1) & 0x55555555); |
| v = (v & 0x33333333) + ((v >>> 2) & 0x33333333); |
| r = ((v + (v >>> 4) & 0xF0F0F0F) * 0x1010101) >>> 24; |
| return r+1; |
| } |
| |
| /* this = -this mod Modulus */ |
| public void neg() |
| { |
| int sb; |
| BIG m=new BIG(p); |
| |
| norm(); |
| sb=logb2((int)BIG.EXCESS(x)); |
| /* |
| ov=BIG.EXCESS(x); |
| sb=1; while(ov!=0) {sb++;ov>>=1;} |
| */ |
| m.fshl(sb); |
| x.rsub(m); |
| |
| if (BIG.EXCESS(x)>=ROM.FEXCESS) reduce(); |
| } |
| |
| /* this-=b */ |
| public void sub(FP b) |
| { |
| FP n=new FP(b); |
| n.neg(); |
| this.add(n); |
| } |
| |
| /* this/=2 mod Modulus */ |
| public void div2() |
| { |
| x.norm(); |
| if (x.parity()==0) |
| x.fshr(1); |
| else |
| { |
| x.add(p); |
| x.norm(); |
| x.fshr(1); |
| } |
| } |
| |
| /* this=1/this mod Modulus */ |
| public void inverse() |
| { |
| BIG r=redc(); |
| r.invmodp(p); |
| x.copy(r); |
| nres(); |
| } |
| |
| /* return TRUE if this==a */ |
| public boolean equals(FP a) |
| { |
| a.reduce(); |
| reduce(); |
| if (BIG.comp(a.x,x)==0) return true; |
| return false; |
| } |
| |
| /* reduce this mod Modulus */ |
| public void reduce() |
| { |
| x.mod(p); |
| } |
| |
| /* return this^e mod Modulus */ |
| public FP pow(BIG e) |
| { |
| int bt; |
| FP r=new FP(1); |
| e.norm(); |
| x.norm(); |
| FP m=new FP(this); |
| while (true) |
| { |
| bt=e.parity(); |
| e.fshr(1); |
| if (bt==1) r.mul(m); |
| if (e.iszilch()) break; |
| m.sqr(); |
| } |
| r.x.mod(p); |
| return r; |
| } |
| |
| /* return sqrt(this) mod Modulus */ |
| public FP sqrt() |
| { |
| reduce(); |
| BIG b=new BIG(p); |
| if (ROM.MOD8==5) |
| { |
| b.dec(5); b.norm(); b.shr(3); |
| FP i=new FP(this); i.x.shl(1); |
| FP v=i.pow(b); |
| i.mul(v); i.mul(v); |
| i.x.dec(1); |
| FP r=new FP(this); |
| r.mul(v); r.mul(i); |
| r.reduce(); |
| return r; |
| } |
| else |
| { |
| b.inc(1); b.norm(); b.shr(2); |
| return pow(b); |
| } |
| } |
| |
| /* return jacobi symbol (this/Modulus) */ |
| public int jacobi() |
| { |
| BIG w=redc(); |
| return w.jacobi(p); |
| } |
| /* |
| public static void main(String[] args) { |
| BIG m=new BIG(ROM.Modulus); |
| BIG x=new BIG(3); |
| BIG e=new BIG(m); |
| e.dec(1); |
| |
| System.out.println("m= "+m.nbits()); |
| |
| |
| BIG r=x.powmod(e,m); |
| |
| System.out.println("m= "+m.toString()); |
| System.out.println("r= "+r.toString()); |
| |
| BIG.cswap(m,r,0); |
| |
| System.out.println("m= "+m.toString()); |
| System.out.println("r= "+r.toString()); |
| |
| // FP y=new FP(3); |
| // FP s=y.pow(e); |
| // System.out.println("s= "+s.toString()); |
| |
| } */ |
| } |