| /* |
| 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. |
| */ |
| |
| package XXX |
| |
| //import "fmt" |
| //import "os" |
| import "github.com/milagro-crypto/amcl/version3/go/amcl" |
| |
| //var debug bool = false |
| |
| const FFLEN int=@ML@ |
| |
| const FF_BITS int=(BIGBITS*FFLEN) /* Finite Field Size in bits - must be 256.2^n */ |
| const HFLEN int=(FFLEN/2) /* Useful for half-size RSA private key operations */ |
| |
| const P_MBITS uint=MODBYTES*8 |
| const P_OMASK Chunk=(Chunk(-1)<<(P_MBITS%BASEBITS)) |
| const P_FEXCESS Chunk=(Chunk(1)<<(BASEBITS*uint(NLEN)-P_MBITS-1)) |
| const P_TBITS uint=(P_MBITS%BASEBITS) |
| |
| func FF_EXCESS(a* BIG) Chunk { |
| return ((a.w[NLEN-1]&P_OMASK)>>(P_TBITS))+1 |
| } |
| |
| /***************** Start 64-bit specific code ****************/ |
| |
| func ff_pexceed(a *BIG,b *BIG) bool { |
| ea:=FF_EXCESS(a) |
| eb:=FF_EXCESS(b) |
| if (ea+1)>P_FEXCESS/(eb+1) {return true} |
| return false |
| } |
| |
| func ff_sexceed(a *BIG) bool { |
| ea:=FF_EXCESS(a) |
| if (ea+1)>P_FEXCESS/(ea+1) {return true} |
| return false |
| } |
| |
| /***************** End 64-bit specific code ****************/ |
| |
| |
| type FF struct { |
| length int |
| v []*BIG |
| } |
| |
| /* Constructors */ |
| func NewFFint(n int) *FF { |
| F:=new(FF) |
| for i:=0;i<n;i++ { |
| F.v=append(F.v,NewBIG()) |
| } |
| F.length=n |
| return F |
| } |
| /* |
| func NewFFints(x [][NLEN]int64,n int) *FF { |
| F:=new(FF) |
| for i:=0;i<n;i++ { |
| F.v=append(F.v,NewBIGints(x[i])) |
| } |
| F.length=n |
| return F |
| } |
| */ |
| /* set to zero */ |
| func (F *FF) zero() { |
| for i:=0;i<F.length;i++ { |
| F.v[i].zero() |
| } |
| } |
| |
| |
| |
| func (F *FF) getlen() int { |
| return F.length |
| } |
| |
| /* set to integer */ |
| func (F *FF) set(m int) { |
| F.zero() |
| F.v[0].set(0,Chunk(m)) |
| } |
| |
| /* copy from FF b */ |
| func (F *FF) copy(b *FF) { |
| for i:=0;i<F.length;i++ { |
| F.v[i].copy(b.v[i]) |
| } |
| } |
| |
| /* x=y<<n */ |
| func (F *FF) dsucopy(b *FF) { |
| for i:=0;i<b.length;i++ { |
| F.v[b.length+i].copy(b.v[i]) |
| F.v[i].zero() |
| } |
| } |
| |
| /* x=y */ |
| func (F *FF) dscopy(b *FF) { |
| for i:=0;i<b.length;i++ { |
| F.v[i].copy(b.v[i]) |
| F.v[b.length+i].zero() |
| } |
| } |
| |
| /* x=y>>n */ |
| func (F *FF) sducopy(b *FF) { |
| for i:=0;i<F.length;i++ { |
| F.v[i].copy(b.v[F.length+i]) |
| } |
| } |
| |
| func (F *FF) one() { |
| F.v[0].one(); |
| for i:=1;i<F.length;i++ { |
| F.v[i].zero() |
| } |
| } |
| |
| /* test equals 0 */ |
| func (F *FF) iszilch() bool { |
| for i:=0;i<F.length;i++ { |
| if !F.v[i].iszilch() {return false} |
| } |
| return true |
| } |
| |
| /* shift right by BIGBITS-bit words */ |
| func (F *FF) shrw(n int) { |
| for i:=0;i<n;i++ { |
| F.v[i].copy(F.v[i+n]) |
| F.v[i+n].zero() |
| } |
| } |
| |
| /* shift left by BIGBITS-bit words */ |
| func (F *FF) shlw(n int) { |
| for i:=0;i<n;i++ { |
| F.v[n+i].copy(F.v[i]) |
| F.v[i].zero() |
| } |
| } |
| |
| /* extract last bit */ |
| func (F *FF) parity() int { |
| return F.v[0].parity() |
| } |
| |
| func (F *FF) lastbits(m int) int { |
| return F.v[0].lastbits(m) |
| } |
| |
| /* compare x and y - must be normalised, and of same length */ |
| func ff_comp(a *FF,b *FF) int { |
| for i:=a.length-1;i>=0;i-- { |
| j:=Comp(a.v[i],b.v[i]) |
| if j!=0 {return j} |
| } |
| return 0 |
| } |
| |
| /* recursive add */ |
| func (F *FF) radd(vp int,x *FF,xp int,y *FF,yp int,n int) { |
| for i:=0;i<n;i++ { |
| F.v[vp+i].copy(x.v[xp+i]) |
| F.v[vp+i].add(y.v[yp+i]) |
| } |
| } |
| |
| /* recursive inc */ |
| func (F *FF) rinc(vp int,y *FF,yp int,n int) { |
| for i:=0;i<n;i++ { |
| F.v[vp+i].add(y.v[yp+i]) |
| } |
| } |
| |
| /* recursive sub */ |
| func (F *FF) rsub(vp int,x *FF,xp int,y *FF,yp int,n int) { |
| for i:=0;i<n;i++ { |
| F.v[vp+i].copy(x.v[xp+i]) |
| F.v[vp+i].sub(y.v[yp+i]) |
| } |
| } |
| |
| /* recursive dec */ |
| func (F *FF) rdec(vp int,y *FF,yp int,n int) { |
| for i:=0;i<n;i++ { |
| F.v[vp+i].sub(y.v[yp+i]) |
| } |
| } |
| |
| /* simple add */ |
| func (F *FF) add(b *FF) { |
| for i:=0;i<F.length;i++ { |
| F.v[i].add(b.v[i]) |
| } |
| } |
| |
| /* simple sub */ |
| func (F *FF) sub(b *FF) { |
| for i:=0;i<F.length;i++ { |
| F.v[i].sub(b.v[i]) |
| } |
| } |
| |
| /* reverse sub */ |
| func (F *FF) revsub(b *FF) { |
| for i:=0;i<F.length;i++ { |
| F.v[i].rsub(b.v[i]) |
| } |
| } |
| |
| /* normalise - but hold any overflow in top part unless n<0 */ |
| func (F *FF) rnorm(vp int,n int) { |
| trunc:=false |
| var carry Chunk |
| if n<0 { /* -v n signals to do truncation */ |
| n=-n |
| trunc=true |
| } |
| for i:=0;i<n-1;i++ { |
| carry=F.v[vp+i].norm() |
| F.v[vp+i].xortop(carry<<P_TBITS) |
| F.v[vp+i+1].w[0]+=carry; // inc(carry) |
| } |
| carry=F.v[vp+n-1].norm() |
| if trunc { |
| F.v[vp+n-1].xortop(carry<<P_TBITS) |
| } |
| } |
| |
| func (F *FF) norm() { |
| F.rnorm(0,F.length) |
| } |
| |
| /* increment/decrement by a small integer */ |
| func (F *FF) inc(m int) { |
| F.v[0].inc(m) |
| F.norm() |
| } |
| |
| func (F *FF) dec(m int) { |
| F.v[0].dec(m) |
| F.norm() |
| } |
| |
| /* shift left by one bit */ |
| func (F *FF) shl() { |
| var delay_carry int=0 |
| for i:=0;i<F.length-1;i++ { |
| carry:=F.v[i].fshl(1) |
| F.v[i].inc(delay_carry) |
| F.v[i].xortop(Chunk(carry)<<P_TBITS) |
| delay_carry=int(carry) |
| } |
| F.v[F.length-1].fshl(1) |
| F.v[F.length-1].inc(delay_carry) |
| } |
| |
| /* shift right by one bit */ |
| |
| func (F *FF) shr() { |
| for i:=F.length-1;i>0;i-- { |
| carry:=F.v[i].fshr(1) |
| F.v[i-1].xortop(Chunk(carry)<<P_TBITS) |
| } |
| F.v[0].fshr(1) |
| } |
| |
| /* Convert to Hex String */ |
| func (F *FF) toString() string { |
| F.norm() |
| s:="" |
| for i:=F.length-1;i>=0;i-- { |
| s+=F.v[i].ToString() |
| } |
| return s |
| } |
| |
| /* Convert FFs to/from byte arrays */ |
| func (F *FF) toBytes(b []byte) { |
| for i:=0;i<F.length;i++ { |
| F.v[i].tobytearray(b,(F.length-i-1)*int(MODBYTES)) |
| } |
| } |
| |
| func ff_fromBytes(x *FF,b []byte) { |
| for i:=0;i<x.length;i++ { |
| x.v[i]=frombytearray(b,(x.length-i-1)*int(MODBYTES)) |
| } |
| } |
| |
| /* in-place swapping using xor - side channel resistant - lengths must be the same */ |
| func ff_cswap(a *FF,b *FF,d int) { |
| for i:=0;i<a.length;i++ { |
| a.v[i].cswap(b.v[i],d) |
| } |
| } |
| |
| /* z=x*y, t is workspace */ |
| func (F *FF) karmul(vp int,x *FF,xp int,y *FF,yp int,t *FF,tp int,n int) { |
| if n==1 { |
| x.v[xp].norm() |
| y.v[yp].norm() |
| d:=mul(x.v[xp],y.v[yp]) |
| F.v[vp+1]=d.split(8*MODBYTES) |
| F.v[vp].dcopy(d) |
| return |
| } |
| nd2:=n/2 |
| F.radd(vp,x,xp,x,xp+nd2,nd2) |
| F.rnorm(vp,nd2) |
| F.radd(vp+nd2,y,yp,y,yp+nd2,nd2) |
| F.rnorm(vp+nd2,nd2) |
| t.karmul(tp,F,vp,F,vp+nd2,t,tp+n,nd2) |
| F.karmul(vp,x,xp,y,yp,t,tp+n,nd2) |
| F.karmul(vp+n,x,xp+nd2,y,yp+nd2,t,tp+n,nd2) |
| t.rdec(tp,F,vp,n) |
| t.rdec(tp,F,vp+n,n) |
| F.rinc(vp+nd2,t,tp,n) |
| F.rnorm(vp,2*n) |
| } |
| |
| func (F *FF) karsqr(vp int,x *FF,xp int,t *FF,tp int,n int) { |
| if n==1 { |
| x.v[xp].norm() |
| d:=sqr(x.v[xp]) |
| F.v[vp+1].copy(d.split(8*MODBYTES)) |
| F.v[vp].dcopy(d) |
| return |
| } |
| |
| nd2:=n/2 |
| F.karsqr(vp,x,xp,t,tp+n,nd2) |
| F.karsqr(vp+n,x,xp+nd2,t,tp+n,nd2) |
| t.karmul(tp,x,xp,x,xp+nd2,t,tp+n,nd2) |
| F.rinc(vp+nd2,t,tp,n) |
| F.rinc(vp+nd2,t,tp,n) |
| F.rnorm(vp+nd2,n) |
| } |
| |
| /* Calculates Least Significant bottom half of x*y */ |
| func (F *FF) karmul_lower(vp int,x *FF,xp int,y *FF,yp int,t *FF,tp int,n int) { |
| if n==1 { /* only calculate bottom half of product */ |
| F.v[vp].copy(smul(x.v[xp],y.v[yp])) |
| return |
| } |
| nd2:=n/2 |
| |
| F.karmul(vp,x,xp,y,yp,t,tp+n,nd2) |
| t.karmul_lower(tp,x,xp+nd2,y,yp,t,tp+n,nd2) |
| F.rinc(vp+nd2,t,tp,nd2) |
| t.karmul_lower(tp,x,xp,y,yp+nd2,t,tp+n,nd2) |
| F.rinc(vp+nd2,t,tp,nd2) |
| F.rnorm(vp+nd2,-nd2) /* truncate it */ |
| } |
| |
| /* Calculates Most Significant upper half of x*y, given lower part */ |
| func (F *FF) karmul_upper(x *FF,y *FF,t *FF,n int) { |
| nd2:=n/2 |
| F.radd(n,x,0,x,nd2,nd2) |
| F.radd(n+nd2,y,0,y,nd2,nd2) |
| F.rnorm(n,nd2) |
| F.rnorm(n+nd2,nd2) |
| |
| t.karmul(0,F,n+nd2,F,n,t,n,nd2) /* t = (a0+a1)(b0+b1) */ |
| F.karmul(n,x,nd2,y,nd2,t,n,nd2) /* z[n]= a1*b1 */ |
| |
| /* z[0-nd2]=l(a0b0) z[nd2-n]= h(a0b0)+l(t)-l(a0b0)-l(a1b1) */ |
| t.rdec(0,F,n,n) /* t=t-a1b1 */ |
| |
| F.rinc(nd2,F,0,nd2) /* z[nd2-n]+=l(a0b0) = h(a0b0)+l(t)-l(a1b1) */ |
| F.rdec(nd2,t,0,nd2) /* z[nd2-n]=h(a0b0)+l(t)-l(a1b1)-l(t-a1b1)=h(a0b0) */ |
| |
| F.rnorm(0,-n) /* a0b0 now in z - truncate it */ |
| |
| t.rdec(0,F,0,n) /* (a0+a1)(b0+b1) - a0b0 */ |
| F.rinc(nd2,t,0,n) |
| |
| F.rnorm(nd2,n) |
| } |
| |
| /* z=x*y. Assumes x and y are of same length. */ |
| func ff_mul(x *FF,y *FF) *FF { |
| n:=x.length |
| z:=NewFFint(2*n) |
| t:=NewFFint(2*n) |
| z.karmul(0,x,0,y,0,t,0,n) |
| return z |
| } |
| |
| /* return low part of product this*y */ |
| func (F *FF) lmul(y *FF) { |
| n:=F.length |
| t:=NewFFint(2*n) |
| x:=NewFFint(n); x.copy(F) |
| F.karmul_lower(0,x,0,y,0,t,0,n) |
| } |
| |
| /* Set b=b mod c */ |
| func (F *FF) mod(c *FF) { |
| var k int=1 |
| |
| F.norm() |
| if ff_comp(F,c)<0 {return} |
| |
| c.shl() |
| for ff_comp(F,c)>=0 { |
| c.shl() |
| k++ |
| } |
| |
| for k>0 { |
| c.shr() |
| if ff_comp(F,c)>=0 { |
| F.sub(c) |
| F.norm() |
| } |
| k-- |
| } |
| } |
| |
| /* z=x^2 */ |
| func ff_sqr(x *FF) *FF { |
| n:=x.length |
| z:=NewFFint(2*n) |
| t:=NewFFint(2*n) |
| z.karsqr(0,x,0,t,0,n) |
| return z |
| } |
| |
| /* return This mod modulus, N is modulus, ND is Montgomery Constant */ |
| func (F *FF) reduce(N *FF,ND *FF) *FF { /* fast karatsuba Montgomery reduction */ |
| n:=N.length |
| t:=NewFFint(2*n) |
| r:=NewFFint(n) |
| m:=NewFFint(n) |
| |
| r.sducopy(F) |
| m.karmul_lower(0,F,0,ND,0,t,0,n) |
| |
| F.karmul_upper(N,m,t,n) |
| |
| m.sducopy(F) |
| r.add(N) |
| r.sub(m) |
| r.norm() |
| |
| return r |
| |
| } |
| |
| /* Set r=this mod b */ |
| /* this is of length - 2*n */ |
| /* r,b is of length - n */ |
| func (F *FF) dmod(b *FF) *FF { |
| n:=b.length |
| m:=NewFFint(2*n) |
| x:=NewFFint(2*n) |
| r:=NewFFint(n) |
| |
| x.copy(F) |
| x.norm() |
| m.dsucopy(b); k:=BIGBITS*n |
| |
| for ff_comp(x,m)>=0 { |
| x.sub(m) |
| x.norm() |
| } |
| |
| for k>0 { |
| m.shr() |
| |
| if ff_comp(x,m)>=0 { |
| x.sub(m) |
| x.norm() |
| } |
| k-- |
| } |
| |
| r.copy(x) |
| r.mod(b) |
| return r |
| } |
| |
| /* Set return=1/this mod p. Binary method - a<p on entry */ |
| |
| func (F *FF) invmodp(p *FF) { |
| n:=p.length |
| |
| u:=NewFFint(n) |
| v:=NewFFint(n) |
| x1:=NewFFint(n) |
| x2:=NewFFint(n) |
| t:=NewFFint(n) |
| one:=NewFFint(n) |
| |
| one.one() |
| u.copy(F) |
| v.copy(p) |
| x1.copy(one) |
| x2.zero() |
| |
| // reduce n in here as well! |
| for (ff_comp(u,one)!=0 && ff_comp(v,one)!=0) { |
| for u.parity()==0 { |
| u.shr() |
| if x1.parity()!=0 { |
| x1.add(p) |
| x1.norm() |
| } |
| x1.shr() |
| } |
| for v.parity()==0 { |
| v.shr() |
| if x2.parity()!=0 { |
| x2.add(p) |
| x2.norm() |
| } |
| x2.shr() |
| } |
| if ff_comp(u,v)>=0 { |
| u.sub(v) |
| u.norm() |
| if ff_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 ff_comp(x2,x1)>=0 { |
| x2.sub(x1) |
| } else { |
| t.copy(p) |
| t.sub(x1) |
| x2.add(t) |
| } |
| x2.norm() |
| } |
| } |
| if ff_comp(u,one)==0 { |
| F.copy(x1) |
| } else { |
| F.copy(x2) |
| } |
| } |
| |
| /* nresidue mod m */ |
| func (F *FF) nres(m *FF) { |
| n:=m.length |
| if n==1 { |
| d:=NewDBIGscopy(F.v[0]) |
| d.shl(uint(NLEN)*BASEBITS) |
| F.v[0].copy(d.mod(m.v[0])) |
| } else { |
| d:=NewFFint(2*n) |
| d.dsucopy(F) |
| F.copy(d.dmod(m)) |
| } |
| } |
| |
| func (F *FF) redc(m *FF,ND *FF) { |
| n:=m.length |
| if n==1 { |
| d:=NewDBIGscopy(F.v[0]) |
| F.v[0].copy(monty(m.v[0],(Chunk(1)<<BASEBITS)-ND.v[0].w[0],d)) |
| } else { |
| d:=NewFFint(2*n) |
| F.mod(m) |
| d.dscopy(F) |
| F.copy(d.reduce(m,ND)) |
| F.mod(m) |
| } |
| } |
| |
| func (F *FF) mod2m(m int) { |
| for i:=m;i<F.length;i++ { |
| F.v[i].zero() |
| } |
| } |
| |
| /* U=1/a mod 2^m - Arazi & Qi */ |
| func (F *FF) invmod2m() *FF { |
| n:=F.length |
| |
| b:=NewFFint(n) |
| c:=NewFFint(n) |
| U:=NewFFint(n) |
| |
| U.zero() |
| U.v[0].copy(F.v[0]) |
| U.v[0].invmod2m() |
| |
| for i:=1;i<n;i<<=1 { |
| b.copy(F); b.mod2m(i) |
| t:=ff_mul(U,b); t.shrw(i); b.copy(t) |
| c.copy(F); c.shrw(i); c.mod2m(i) |
| c.lmul(U); c.mod2m(i) |
| |
| b.add(c); b.norm() |
| b.lmul(U); b.mod2m(i) |
| |
| c.one(); c.shlw(i); b.revsub(c); b.norm() |
| b.shlw(i) |
| U.add(b) |
| } |
| U.norm() |
| return U |
| } |
| |
| func (F *FF) random(rng *amcl.RAND) { |
| n:=F.length |
| for i:=0;i<n;i++ { |
| F.v[i].copy(random(rng)) |
| } |
| /* make sure top bit is 1 */ |
| for (F.v[n-1].nbits()<int(MODBYTES*8)) { |
| F.v[n-1].copy(random(rng)) |
| } |
| } |
| |
| /* generate random x less than p */ |
| func (F *FF) randomnum(p *FF,rng *amcl.RAND) { |
| n:=F.length |
| d:=NewFFint(2*n) |
| |
| for i:=0;i<2*n;i++ { |
| d.v[i].copy(random(rng)) |
| } |
| F.copy(d.dmod(p)) |
| } |
| |
| /* this*=y mod p */ |
| func (F *FF) modmul(y *FF,p *FF,nd *FF) { |
| if ff_pexceed(F.v[F.length-1],y.v[y.length-1]) {F.mod(p)} |
| n:=p.length |
| if n==1 { |
| d:=mul(F.v[0],y.v[0]) |
| F.v[0].copy(monty(p.v[0],(Chunk(1)<<BASEBITS)-nd.v[0].w[0],d)) |
| } else { |
| d:=ff_mul(F,y) |
| F.copy(d.reduce(p,nd)) |
| } |
| } |
| |
| /* this*=y mod p */ |
| func (F *FF) modsqr(p *FF,nd *FF) { |
| if ff_sexceed(F.v[F.length-1]) {F.mod(p)} |
| n:=p.length |
| if n==1 { |
| d:=sqr(F.v[0]) |
| F.v[0].copy(monty(p.v[0],(Chunk(1)<<BASEBITS)-nd.v[0].w[0],d)) |
| } else { |
| d:=ff_sqr(F) |
| F.copy(d.reduce(p,nd)) |
| } |
| } |
| |
| /* this=this^e mod p using side-channel resistant Montgomery Ladder, for large e */ |
| func (F *FF) skpow(e *FF,p *FF) { |
| n:=p.length |
| R0:=NewFFint(n) |
| R1:=NewFFint(n) |
| ND:=p.invmod2m() |
| |
| F.mod(p) |
| R0.one() |
| R1.copy(F) |
| R0.nres(p) |
| R1.nres(p) |
| |
| for i:=int(8*MODBYTES)*n-1;i>=0;i-- { |
| b:=int(e.v[i/BIGBITS].bit(i%BIGBITS)) |
| F.copy(R0) |
| F.modmul(R1,p,ND) |
| |
| ff_cswap(R0,R1,b) |
| R0.modsqr(p,ND) |
| |
| R1.copy(F) |
| ff_cswap(R0,R1,b) |
| } |
| F.copy(R0) |
| F.redc(p,ND) |
| } |
| |
| /* this =this^e mod p using side-channel resistant Montgomery Ladder, for short e */ |
| func (F *FF) skpows(e *BIG,p *FF) { |
| n:=p.length |
| R0:=NewFFint(n) |
| R1:=NewFFint(n) |
| ND:=p.invmod2m() |
| |
| F.mod(p) |
| R0.one() |
| R1.copy(F) |
| R0.nres(p) |
| R1.nres(p) |
| |
| for i:=int(8*MODBYTES)-1;i>=0;i-- { |
| b:=int(e.bit(i)) |
| F.copy(R0) |
| F.modmul(R1,p,ND) |
| |
| ff_cswap(R0,R1,b) |
| R0.modsqr(p,ND) |
| |
| R1.copy(F) |
| ff_cswap(R0,R1,b) |
| } |
| F.copy(R0) |
| F.redc(p,ND) |
| } |
| |
| /* raise to an integer power - right-to-left method */ |
| func (F *FF) power(e int,p *FF) { |
| n:=p.length |
| w:=NewFFint(n) |
| ND:=p.invmod2m() |
| f:=true |
| |
| w.copy(F) |
| w.nres(p) |
| //i:=0; |
| if e==2 { |
| F.copy(w) |
| F.modsqr(p,ND) |
| } else { |
| for (true) { |
| if e%2==1 { |
| if f { |
| F.copy(w) |
| } else {F.modmul(w,p,ND)} |
| f=false |
| |
| } |
| e>>=1 |
| if e==0 {break} |
| //fmt.Printf("wb= "+w.toString()+"\n"); |
| //debug=true; |
| w.modsqr(p,ND) |
| //debug=false; |
| //fmt.Printf("wa= "+w.toString()+"\n"); |
| //i+=1; |
| //os.Exit(0); |
| } |
| } |
| |
| F.redc(p,ND) |
| |
| } |
| |
| /* this=this^e mod p, faster but not side channel resistant */ |
| func (F *FF) pow(e *FF,p *FF) { |
| n:=p.length |
| w:=NewFFint(n) |
| ND:=p.invmod2m() |
| //fmt.Printf("ND= "+ND.toString() +"\n"); |
| w.copy(F) |
| F.one() |
| F.nres(p) |
| w.nres(p) |
| for i:=int(8*MODBYTES)*n-1;i>=0;i-- { |
| F.modsqr(p,ND) |
| b:=e.v[i/BIGBITS].bit(i%BIGBITS) |
| if b==1 {F.modmul(w,p,ND)} |
| } |
| F.redc(p,ND) |
| } |
| |
| /* double exponentiation r=x^e.y^f mod p */ |
| func (F *FF) pow2(e *BIG,y *FF,f *BIG,p *FF) { |
| n:=p.length |
| xn:=NewFFint(n) |
| yn:=NewFFint(n) |
| xy:=NewFFint(n) |
| ND:=p.invmod2m() |
| |
| xn.copy(F) |
| yn.copy(y) |
| xn.nres(p) |
| yn.nres(p) |
| xy.copy(xn); xy.modmul(yn,p,ND) |
| F.one() |
| F.nres(p) |
| |
| for i:=int(8*MODBYTES)-1;i>=0;i-- { |
| eb:=e.bit(i) |
| fb:=f.bit(i) |
| F.modsqr(p,ND) |
| if eb==1 { |
| if fb==1 { |
| F.modmul(xy,p,ND) |
| } else {F.modmul(xn,p,ND)} |
| } else { |
| if fb==1 {F.modmul(yn,p,ND)} |
| } |
| } |
| F.redc(p,ND) |
| } |
| |
| func igcd(x int,y int) int { /* integer GCD, returns GCD of x and y */ |
| var r int |
| if y==0 {return x} |
| for true { |
| r=x%y |
| if r==0 {break} |
| x=y;y=r |
| } |
| return y |
| } |
| |
| /* quick and dirty check for common factor with n */ |
| func (F *FF) cfactor(s int) bool { |
| n:=F.length |
| |
| x:=NewFFint(n) |
| y:=NewFFint(n) |
| |
| y.set(s) |
| x.copy(F) |
| x.norm() |
| |
| x.sub(y) |
| x.norm() |
| |
| for (!x.iszilch() && x.parity()==0) {x.shr()} |
| |
| for (ff_comp(x,y)>0) { |
| x.sub(y) |
| x.norm() |
| for (!x.iszilch() && x.parity()==0) {x.shr()} |
| } |
| |
| g:=int(x.v[0].get(0)) |
| r:=igcd(s,g) |
| if r>1 {return true} |
| return false |
| } |
| |
| /* Miller-Rabin test for primality. Slow. */ |
| func prime(p *FF,rng *amcl.RAND) bool { |
| s:=0 |
| n:=p.length |
| d:=NewFFint(n) |
| x:=NewFFint(n) |
| unity:=NewFFint(n) |
| nm1:=NewFFint(n) |
| |
| sf:=4849845 /* 3*5*.. *19 */ |
| p.norm() |
| |
| if p.cfactor(sf) {return false} |
| unity.one() |
| nm1.copy(p) |
| nm1.sub(unity) |
| nm1.norm() |
| d.copy(nm1) |
| |
| for d.parity()==0 { |
| d.shr() |
| s++ |
| } |
| if s==0 {return false} |
| |
| for i:=0;i<10;i++ { |
| x.randomnum(p,rng) |
| x.pow(d,p) |
| |
| if (ff_comp(x,unity)==0 || ff_comp(x,nm1)==0) {continue} |
| loop:=false |
| for j:=1;j<s;j++ { |
| x.power(2,p) |
| if ff_comp(x,unity)==0 {return false} |
| if ff_comp(x,nm1)==0 {loop=true; break} |
| } |
| if loop {continue} |
| return false |
| } |
| |
| return true |
| } |
| /* |
| func main() { |
| |
| var P = [4][5]int64 {{0xAD19A781670957,0x76A79C00965796,0xDEFCC5FC9A9717,0xF02F2940E20E9,0xBF59E34F},{0x6894F31844C908,0x8DADA70E82C79F,0xFD29F3836046F6,0x8C1D874D314DD0,0x46D077B},{0x3C515217813331,0x56680FD1CE935B,0xE55C53EEA8838E,0x92C2F7E14A4A95,0xD945E5B1},{0xACF673E919F5EF,0x6723E7E7DAB446,0x6B6FA69B36EB1B,0xF7D13920ECA300,0xB5FC2165}} |
| |
| fmt.Printf("Testing FF\n") |
| var raw [100]byte |
| rng:=NewRAND() |
| |
| rng.Clean() |
| for i:=0;i<100;i++ { |
| raw[i]=byte(i) |
| } |
| |
| rng.Seed(100,raw[:]) |
| |
| n:=4 |
| |
| x:=NewFFint(n) |
| x.set(3) |
| |
| p:=NewFFints(P[:],n) |
| |
| if prime(p,rng) {fmt.Printf("p is a prime\n"); fmt.Printf("\n")} |
| |
| e:=NewFFint(n) |
| e.copy(p) |
| e.dec(1); e.norm() |
| |
| fmt.Printf("e= "+e.toString()) |
| fmt.Printf("\n") |
| x.skpow(e,p) |
| fmt.Printf("x= "+x.toString()) |
| fmt.Printf("\n") |
| } |
| */ |