| /* |
| 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 */ |
| /* CLINT mod p functions */ |
| |
| package XXX |
| |
| //import "fmt" |
| |
| const NOT_SPECIAL int=0 |
| const PSEUDO_MERSENNE int=1 |
| const MONTGOMERY_FRIENDLY int=2 |
| const GENERALISED_MERSENNE int=3 |
| |
| const MODBITS uint=@NBT@ /* Number of bits in Modulus */ |
| const MOD8 uint=@M8@ /* Modulus mod 8 */ |
| const MODTYPE int=@MT@ //NOT_SPECIAL |
| |
| const FEXCESS int32=((int32(1)<<@SH@)-1) |
| const OMASK Chunk= ((Chunk(-1))<<(MODBITS%BASEBITS)) |
| const TBITS uint=MODBITS%BASEBITS // Number of active bits in top word |
| const TMASK Chunk=(Chunk(1)<<TBITS)-1 |
| |
| |
| type FP struct { |
| x *BIG |
| XES int32 |
| } |
| |
| /* Constructors */ |
| func NewFPint(a int) *FP { |
| F:=new(FP) |
| F.x=NewBIGint(a) |
| F.nres() |
| return F |
| } |
| |
| func NewFPbig(a *BIG) *FP { |
| F:=new(FP) |
| F.x=NewBIGcopy(a) |
| F.nres() |
| return F |
| } |
| |
| func NewFPcopy(a *FP) *FP { |
| F:=new(FP) |
| F.x=NewBIGcopy(a.x) |
| F.XES=a.XES |
| return F |
| } |
| |
| func (F *FP) toString() string { |
| F.reduce() |
| return F.redc().ToString() |
| } |
| |
| /* convert to Montgomery n-residue form */ |
| func (F *FP) nres() { |
| if MODTYPE!=PSEUDO_MERSENNE && MODTYPE!=GENERALISED_MERSENNE { |
| r:=NewBIGints(R2modp) |
| d:=mul(F.x,r) |
| F.x.copy(mod(d)) |
| F.XES=2 |
| } else { |
| F.XES=1 |
| } |
| } |
| |
| /* convert back to regular form */ |
| func (F *FP) redc() *BIG { |
| if MODTYPE!=PSEUDO_MERSENNE && MODTYPE!=GENERALISED_MERSENNE { |
| d:=NewDBIGscopy(F.x) |
| return mod(d) |
| } else { |
| r:=NewBIGcopy(F.x) |
| return r |
| } |
| } |
| |
| /* reduce a DBIG to a BIG using the appropriate form of the modulus */ |
| |
| func mod(d *DBIG) *BIG { |
| if MODTYPE==PSEUDO_MERSENNE { |
| t:=d.split(MODBITS) |
| b:=NewBIGdcopy(d) |
| |
| v:=t.pmul(int(MConst)) |
| |
| t.add(b) |
| t.norm() |
| |
| tw:=t.w[NLEN-1] |
| t.w[NLEN-1]&=TMASK |
| t.w[0]+=(MConst*((tw>>TBITS)+(v<<(BASEBITS-TBITS)))) |
| |
| t.norm() |
| return t |
| // b.add(t) |
| // b.norm() |
| // return b |
| } |
| if MODTYPE==MONTGOMERY_FRIENDLY { |
| for i:=0;i<NLEN;i++ { |
| top,bot:=muladd(d.w[i],MConst-1,d.w[i],d.w[NLEN+i-1]) |
| d.w[NLEN+i-1]=bot |
| d.w[NLEN+i]+=top |
| } |
| b:=NewBIG() |
| |
| for i:=0;i<NLEN;i++ { |
| b.w[i]=d.w[NLEN+i] |
| } |
| b.norm() |
| return b |
| } |
| |
| if MODTYPE==GENERALISED_MERSENNE { // GoldiLocks only |
| t:=d.split(MODBITS) |
| b:=NewBIGdcopy(d) |
| b.add(t); |
| dd:=NewDBIGscopy(t) |
| dd.shl(MODBITS/2) |
| |
| tt:=dd.split(MODBITS) |
| lo:=NewBIGdcopy(dd) |
| b.add(tt) |
| b.add(lo) |
| b.norm() |
| tt.shl(MODBITS/2) |
| b.add(tt) |
| |
| carry:=b.w[NLEN-1]>>TBITS |
| b.w[NLEN-1]&=TMASK |
| b.w[0]+=carry |
| |
| b.w[224/BASEBITS]+=carry<<(224%BASEBITS); |
| b.norm() |
| return b |
| } |
| |
| if MODTYPE==NOT_SPECIAL { |
| md:=NewBIGints(Modulus) |
| return monty(md,MConst,d) |
| } |
| return NewBIG() |
| } |
| |
| // find appoximation to quotient of a/m |
| // Out by at most 2. |
| // Note that MAXXES is bounded to be 2-bits less than half a word |
| func quo(n *BIG,m *BIG) int { |
| var num Chunk |
| var den Chunk |
| hb:=uint(CHUNK)/2 |
| if TBITS < hb { |
| sh:=hb-TBITS |
| num=((n.w[NLEN-1]<<sh))|(n.w[NLEN-2]>>(BASEBITS-sh)) |
| den=((m.w[NLEN-1]<<sh))|(m.w[NLEN-2]>>(BASEBITS-sh)) |
| |
| } else { |
| num=n.w[NLEN-1] |
| den=m.w[NLEN-1] |
| } |
| return int(num/(den+1)) |
| } |
| |
| /* reduce this mod Modulus */ |
| func (F *FP) reduce() { |
| m:=NewBIGints(Modulus) |
| r:=NewBIGints(Modulus) |
| var sb uint |
| F.x.norm() |
| |
| if F.XES > 16 { |
| q:=quo(F.x,m) |
| carry:=r.pmul(q) |
| r.w[NLEN-1]+=carry<<BASEBITS |
| F.x.sub(r) |
| F.x.norm() |
| sb=2 |
| } else { |
| sb=logb2(uint32(F.XES-1)) |
| } |
| |
| m.fshl(sb) |
| for sb>0 { |
| sr:=ssn(r,F.x,m) |
| F.x.cmove(r,1-sr) |
| sb -= 1 |
| } |
| |
| F.XES=1 |
| } |
| |
| /* test this=0? */ |
| func (F *FP) iszilch() bool { |
| W:=NewFPcopy(F) |
| W.reduce() |
| return W.x.iszilch() |
| } |
| |
| /* copy from FP b */ |
| func (F *FP) copy(b *FP ) { |
| F.x.copy(b.x) |
| F.XES=b.XES |
| } |
| |
| /* set this=0 */ |
| func (F *FP) zero() { |
| F.x.zero() |
| F.XES=1 |
| } |
| |
| /* set this=1 */ |
| func (F *FP) one() { |
| F.x.one(); F.nres() |
| } |
| |
| /* normalise this */ |
| func (F *FP) norm() { |
| F.x.norm() |
| } |
| |
| /* swap FPs depending on d */ |
| func (F *FP) cswap(b *FP,d int) { |
| c:=int32(d) |
| c=^(c-1) |
| t:=c&(F.XES^b.XES) |
| F.XES^=t |
| b.XES^=t |
| F.x.cswap(b.x,d) |
| } |
| |
| /* copy FPs depending on d */ |
| func (F *FP) cmove(b *FP,d int) { |
| F.x.cmove(b.x,d) |
| c:=int32(-d) |
| F.XES^=(F.XES^b.XES)&c |
| } |
| |
| /* this*=b mod Modulus */ |
| func (F *FP) mul(b *FP) { |
| |
| if int64(F.XES)*int64(b.XES)>int64(FEXCESS) {F.reduce()} |
| |
| d:=mul(F.x,b.x) |
| F.x.copy(mod(d)) |
| F.XES=2 |
| } |
| |
| /* this = -this mod Modulus */ |
| func (F *FP) neg() { |
| m:=NewBIGints(Modulus) |
| sb:=logb2(uint32(F.XES-1)) |
| |
| m.fshl(sb) |
| F.x.rsub(m) |
| |
| F.XES=(1<<sb)+1 |
| if F.XES>FEXCESS {F.reduce()} |
| } |
| |
| |
| /* this*=c mod Modulus, where c is a small int */ |
| func (F *FP) imul(c int) { |
| // F.norm() |
| s:=false |
| if (c<0) { |
| c=-c |
| s=true |
| } |
| |
| if MODTYPE==PSEUDO_MERSENNE || MODTYPE==GENERALISED_MERSENNE { |
| d:=F.x.pxmul(c) |
| F.x.copy(mod(d)) |
| F.XES=2 |
| } else { |
| if F.XES*int32(c)<=FEXCESS { |
| F.x.pmul(c) |
| F.XES*=int32(c) |
| } else { |
| n:=NewFPint(c) |
| F.mul(n) |
| } |
| } |
| if s {F.neg(); F.norm()} |
| } |
| |
| /* this*=this mod Modulus */ |
| func (F *FP) sqr() { |
| if int64(F.XES)*int64(F.XES)>int64(FEXCESS) {F.reduce()} |
| d:=sqr(F.x) |
| F.x.copy(mod(d)) |
| F.XES=2 |
| } |
| |
| /* this+=b */ |
| func (F *FP) add(b *FP) { |
| F.x.add(b.x) |
| F.XES+=b.XES |
| if (F.XES>FEXCESS) {F.reduce()} |
| } |
| |
| /* this-=b */ |
| func (F *FP) sub(b *FP) { |
| n:=NewFPcopy(b) |
| n.neg() |
| F.add(n) |
| } |
| |
| func (F *FP) rsub(b *FP) { |
| F.neg() |
| F.add(b) |
| } |
| |
| /* this/=2 mod Modulus */ |
| func (F *FP) div2() { |
| // F.x.norm() |
| if (F.x.parity()==0) { |
| F.x.fshr(1) |
| } else { |
| p:=NewBIGints(Modulus); |
| F.x.add(p) |
| F.x.norm() |
| F.x.fshr(1) |
| } |
| } |
| |
| |
| // return this^(p-3)/4 or this^(p-5)/8 |
| func (F *FP) fpow() *FP { |
| ac := [11]int{1, 2, 3, 6, 12, 15, 30, 60, 120, 240,255} |
| var xp []*FP |
| // phase 1 |
| xp=append(xp,NewFPcopy(F)); |
| xp=append(xp,NewFPcopy(F)); xp[1].sqr() |
| xp=append(xp,NewFPcopy(xp[1])); xp[2].mul(F) |
| xp=append(xp,NewFPcopy(xp[2])); xp[3].sqr() |
| xp=append(xp,NewFPcopy(xp[3])); xp[4].sqr() |
| xp=append(xp,NewFPcopy(xp[4])); xp[5].mul(xp[2]) |
| xp=append(xp,NewFPcopy(xp[5])); xp[6].sqr() |
| xp=append(xp,NewFPcopy(xp[6])); xp[7].sqr() |
| xp=append(xp,NewFPcopy(xp[7])); xp[8].sqr() |
| xp=append(xp,NewFPcopy(xp[8])); xp[9].sqr() |
| xp=append(xp,NewFPcopy(xp[9])); xp[10].mul(xp[5]) |
| var n,c int |
| |
| if MOD8==5 { |
| n=int(MODBITS)-3 |
| c=(int(MConst)+5)/8 |
| } else { |
| n=int(MODBITS)-2 |
| c=(int(MConst)+3)/4 |
| |
| } |
| |
| bw:=0; w:=1; for w<c {w*=2; bw+=1} |
| k:=w-c |
| |
| i:=10; key:=NewFPint(0) |
| |
| if k!=0 { |
| for ac[i]>k {i--} |
| key.copy(xp[i]) |
| k-=ac[i] |
| } |
| |
| for k!=0 { |
| i-- |
| if ac[i]>k {continue} |
| key.mul(xp[i]) |
| k-=ac[i] |
| } |
| // phase 2 |
| xp[1].copy(xp[2]) |
| xp[2].copy(xp[5]) |
| xp[3].copy(xp[10]) |
| |
| j:=3; m:=8 |
| nw:=n-bw |
| t:=NewFPint(0) |
| for 2*m<nw { |
| t.copy(xp[j]); j++ |
| for i=0;i<m;i++ {t.sqr()} |
| xp[j].copy(xp[j-1]) |
| xp[j].mul(t) |
| m*=2 |
| } |
| lo:=nw-m |
| r:=NewFPcopy(xp[j]) |
| |
| for lo!=0 { |
| m/=2; j-- |
| if lo<m {continue} |
| lo-=m |
| t.copy(r) |
| for i=0;i<m;i++ {t.sqr()} |
| r.copy(t) |
| r.mul(xp[j]) |
| } |
| // phase 3 |
| for i=0;i<bw;i++ {r.sqr()} |
| |
| if w-c != 0 { |
| r.mul(key) |
| } |
| |
| return r |
| } |
| |
| |
| |
| /* this=1/this mod Modulus */ |
| func (F *FP) inverse() { |
| |
| if MODTYPE==PSEUDO_MERSENNE { |
| y:=F.fpow() |
| if MOD8==5 { |
| t:=NewFPcopy(F) |
| t.sqr() |
| F.mul(t) |
| y.sqr() |
| } |
| y.sqr() |
| y.sqr() |
| F.mul(y) |
| } else { |
| m2:=NewBIGints(Modulus) |
| m2.dec(2); m2.norm() |
| F.copy(F.pow(m2)) |
| } |
| |
| } |
| |
| /* return TRUE if this==a */ |
| func (F *FP) Equals(a *FP) bool { |
| f:=NewFPcopy(F) |
| s:=NewFPcopy(a); |
| |
| s.reduce() |
| f.reduce() |
| if (Comp(s.x,f.x)==0) {return true} |
| return false |
| } |
| |
| /* return this^e mod Modulus */ |
| /* |
| func (F *FP) pow(e *BIG) *FP { |
| r:=NewFPint(1) |
| e.norm() |
| F.norm() |
| m:=NewFPcopy(F) |
| for true { |
| bt:=e.parity() |
| e.fshr(1) |
| if bt==1 {r.mul(m)} |
| if e.iszilch() {break} |
| m.sqr() |
| } |
| r.reduce() |
| return r |
| } |
| */ |
| |
| |
| func (F *FP) pow(e *BIG) *FP { |
| var tb []*FP |
| var w [1+(NLEN*int(BASEBITS)+3)/4]int8 |
| F.norm() |
| t:=NewBIGcopy(e) |
| t.norm() |
| nb:=1+(t.nbits()+3)/4 |
| |
| for i:=0;i<nb;i++ { |
| lsbs:=t.lastbits(4) |
| t.dec(lsbs) |
| t.norm() |
| w[i]=int8(lsbs) |
| t.fshr(4); |
| } |
| tb=append(tb,NewFPint(1)) |
| tb=append(tb,NewFPcopy(F)) |
| for i:=2;i<16;i++ { |
| tb=append(tb,NewFPcopy(tb[i-1])) |
| tb[i].mul(F); |
| } |
| r:=NewFPcopy(tb[w[nb-1]]) |
| for i:=nb-2;i>=0;i-- { |
| r.sqr() |
| r.sqr() |
| r.sqr() |
| r.sqr() |
| r.mul(tb[w[i]]) |
| } |
| r.reduce() |
| return r |
| } |
| |
| |
| /* return sqrt(this) mod Modulus */ |
| func (F *FP) sqrt() *FP { |
| F.reduce(); |
| if MOD8==5 { |
| var v *FP |
| i:=NewFPcopy(F); i.x.shl(1) |
| if MODTYPE==PSEUDO_MERSENNE { |
| v=i.fpow() |
| } else { |
| b:=NewBIGints(Modulus); |
| b.dec(5); b.norm(); b.shr(3) |
| v=i.pow(b) |
| } |
| |
| i.mul(v); i.mul(v) |
| i.x.dec(1) |
| r:=NewFPcopy(F) |
| r.mul(v); r.mul(i) |
| r.reduce() |
| return r |
| } else { |
| var r *FP |
| if MODTYPE==PSEUDO_MERSENNE { |
| r=F.fpow() |
| r.mul(F) |
| } else { |
| b:=NewBIGints(Modulus); |
| b.inc(1); b.norm(); b.shr(2) |
| r=F.pow(b) |
| } |
| return r |
| } |
| } |
| |
| /* return jacobi symbol (this/Modulus) */ |
| func (F *FP) jacobi() int { |
| w:=F.redc(); |
| p:=NewBIGints(Modulus); |
| return w.Jacobi(p) |
| } |