| /* |
| 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. |
| */ |
| // |
| // fp.swift |
| // |
| // Created by Michael Scott on 20/06/2015. |
| // Copyright (c) 2015 Michael Scott. All rights reserved. |
| // Small Finite Field arithmetic |
| // AMCL mod p functions |
| // |
| |
| public struct FP { |
| |
| |
| static public let NOT_SPECIAL=0 |
| static public let PSEUDO_MERSENNE=1 |
| static public let MONTGOMERY_FRIENDLY=2 |
| static public let GENERALISED_MERSENNE=3 |
| |
| static public let MODBITS:UInt = @NBT@ |
| static let MOD8:UInt = @M8@ |
| static public let MODTYPE = @MT@ |
| |
| static let FEXCESS:Int32 = ((Int32(1)<<@SH@)-1) |
| static let OMASK:Chunk=Chunk(-1)<<Chunk(FP.MODBITS%BIG.BASEBITS) |
| static let TBITS:UInt=FP.MODBITS%BIG.BASEBITS; // Number of active bits in top word |
| static let TMASK:Chunk=(1<<Chunk(FP.TBITS))-1 |
| |
| var x:BIG |
| var xes:Int32 |
| static let p=BIG(ROM.Modulus) |
| static let r2modp=BIG(ROM.R2modp) |
| |
| /* convert to Montgomery n-residue form */ |
| mutating func nres() |
| { |
| if FP.MODTYPE != FP.PSEUDO_MERSENNE && FP.MODTYPE != FP.GENERALISED_MERSENNE |
| { |
| var d=BIG.mul(x,FP.r2modp); |
| x.copy(FP.mod(&d)) |
| xes=2 |
| } else {xes=1} |
| } |
| /* convert back to regular form */ |
| func redc() -> BIG |
| { |
| if FP.MODTYPE != FP.PSEUDO_MERSENNE && FP.MODTYPE != FP.GENERALISED_MERSENNE |
| { |
| var d=DBIG(x) |
| return FP.mod(&d) |
| } |
| else |
| { |
| let r=BIG(x) |
| return r; |
| } |
| } |
| |
| /* reduce a DBIG to a BIG using the appropriate form of the modulus */ |
| static func mod(_ d: inout DBIG) -> BIG |
| { |
| |
| if FP.MODTYPE==FP.PSEUDO_MERSENNE |
| { |
| var t=d.split(FP.MODBITS) |
| let b=BIG(d) |
| let v=t.pmul(Int(ROM.MConst)) |
| |
| t.add(b) |
| t.norm() |
| |
| |
| let tw=t.w[BIG.NLEN-1] |
| t.w[BIG.NLEN-1] &= TMASK |
| t.inc(Int(ROM.MConst*((tw>>Chunk(FP.TBITS))+(v<<Chunk(BIG.BASEBITS-FP.TBITS))))) |
| |
| t.norm() |
| return t |
| |
| } |
| if FP.MODTYPE==FP.MONTGOMERY_FRIENDLY |
| { |
| for i in 0 ..< BIG.NLEN { |
| let (top,bot)=BIG.muladd(d.w[i],ROM.MConst-1,d.w[i],d.w[BIG.NLEN+i-1]) |
| d.w[BIG.NLEN+i]+=top; d.w[BIG.NLEN+i-1]=bot |
| // d.w[BIG.NLEN+i]+=d.muladd(d.w[i],ROM.MConst-1,d.w[i],BIG.NLEN+i-1) |
| } |
| |
| var b=BIG(0); |
| |
| for i in 0 ..< BIG.NLEN |
| { |
| b.w[i]=d.w[BIG.NLEN+i] |
| } |
| b.norm() |
| return b; |
| } |
| if FP.MODTYPE==FP.GENERALISED_MERSENNE |
| { // GoldiLocks Only |
| let t=d.split(FP.MODBITS) |
| let RM2=FP.MODBITS/2 |
| var b=BIG(d) |
| b.add(t) |
| var dd=DBIG(t) |
| dd.shl(RM2) |
| |
| var tt=dd.split(FP.MODBITS) |
| let lo=BIG(dd) |
| b.add(tt) |
| b.add(lo) |
| b.norm() |
| tt.shl(RM2) |
| b.add(tt) |
| |
| let carry=b.w[BIG.NLEN-1]>>Chunk(FP.TBITS) |
| b.w[BIG.NLEN-1]&=TMASK |
| b.w[0]+=carry |
| |
| b.w[Int(224/BIG.BASEBITS)]+=carry<<Chunk(224%BIG.BASEBITS) |
| b.norm() |
| return b; |
| } |
| if FP.MODTYPE==FP.NOT_SPECIAL |
| { |
| let md=BIG(ROM.Modulus); |
| |
| return BIG.monty(md,ROM.MConst,&d) |
| } |
| return BIG(0) |
| } |
| |
| |
| init() |
| { |
| x=BIG(0) |
| xes=1 |
| } |
| init(_ a: Int) |
| { |
| x=BIG(a) |
| xes=1 |
| nres() |
| } |
| init(_ a: BIG) |
| { |
| x=BIG(a) |
| xes=1 |
| nres() |
| } |
| init(_ a: FP) |
| { |
| x=BIG(a.x) |
| xes=a.xes |
| } |
| /* convert to string */ |
| func toString() -> String |
| { |
| let s=redc().toString() |
| return s |
| } |
| |
| func toRawString() -> String |
| { |
| let s=x.toRawString() |
| return s |
| } |
| |
| |
| |
| /* reduce this mod Modulus */ |
| mutating func reduce() |
| { |
| |
| var m=BIG(FP.p) |
| var r=BIG(FP.p) |
| var sb:Int |
| |
| x.norm() |
| |
| if xes>16 { |
| let q=FP.quo(x,m) |
| let carry=r.pmul(q) |
| r.w[BIG.NLEN-1]+=carry<<Chunk(BIG.BASEBITS); // correction - put any carry out back in again |
| x.sub(r) |
| x.norm() |
| sb=2 |
| } else { |
| sb=FP.logb2(UInt32(xes-Int32(1))) |
| } |
| m.fshl(sb) |
| |
| while sb>0 { |
| let sr=BIG.ssn(&r,x,&m) |
| x.cmove(r,1-sr) |
| sb -= 1 |
| } |
| |
| xes=1 |
| } |
| |
| /* test this=0? */ |
| func iszilch() -> Bool |
| { |
| var z=FP(self) |
| z.reduce() |
| return z.x.iszilch() |
| } |
| |
| /* copy from FP b */ |
| mutating func copy(_ b: FP) |
| { |
| x.copy(b.x) |
| xes=b.xes |
| } |
| |
| /* set this=0 */ |
| mutating func zero() |
| { |
| x.zero(); |
| xes=1; |
| } |
| |
| /* set this=1 */ |
| mutating func one() |
| { |
| x.one(); nres() |
| } |
| |
| /* normalise this */ |
| mutating func norm() |
| { |
| x.norm(); |
| } |
| /* swap FPs depending on d */ |
| mutating func cswap(_ b: inout FP,_ d: Int) |
| { |
| var c=Int32(d) |
| x.cswap(&(b.x),d) |
| c = ~(c-1) |
| let t=c&(xes^b.xes) |
| xes^=t |
| b.xes^=t |
| } |
| |
| /* copy FPs depending on d */ |
| mutating func cmove(_ b: FP,_ d:Int) |
| { |
| let c=Int32(-d) |
| x.cmove(b.x,d) |
| xes^=(xes^b.xes)&c |
| } |
| /* this*=b mod Modulus */ |
| mutating func mul(_ b: FP) |
| { |
| |
| if Int64(xes)*Int64(b.xes) > Int64(FP.FEXCESS) {reduce()} |
| |
| var d=BIG.mul(x,b.x) |
| x.copy(FP.mod(&d)) |
| xes=2 |
| } |
| static func logb2(_ w: UInt32) -> Int |
| { |
| var v = w |
| 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) |
| let r = Int(( ((v + (v >> 4)) & 0xF0F0F0F) &* 0x1010101) >> 24) |
| return (r) |
| } |
| |
| // 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 |
| static func quo(_ n: BIG,_ m: BIG) -> Int |
| { |
| let hb=UInt(BIG.CHUNK)/2 |
| if FP.TBITS < hb { |
| let sh=Chunk(hb-FP.TBITS); |
| let num=((n.w[BIG.NLEN-1]<<sh))|(n.w[BIG.NLEN-2]>>(Chunk(BIG.BASEBITS)-sh)); |
| let den=((m.w[BIG.NLEN-1]<<sh))|(m.w[BIG.NLEN-2]>>(Chunk(BIG.BASEBITS)-sh)); |
| return Int(num/(den+1)); |
| } else { |
| let num=n.w[BIG.NLEN-1]; |
| let den=m.w[BIG.NLEN-1]; |
| return Int(num/(den+1)); |
| } |
| } |
| |
| /* this = -this mod Modulus */ |
| mutating func neg() |
| { |
| var m=BIG(FP.p) |
| let sb=FP.logb2(UInt32(xes-Int32(1))) |
| m.fshl(sb) |
| x.rsub(m) |
| xes=(1<<Int32(sb))+1 |
| if xes>FP.FEXCESS {reduce()} |
| } |
| /* this*=c mod Modulus, where c is a small int */ |
| mutating func imul(_ c: Int) |
| { |
| var cc=c |
| // norm(); |
| var s=false |
| if (cc<0) |
| { |
| cc = -cc |
| s=true |
| } |
| |
| if FP.MODTYPE==FP.PSEUDO_MERSENNE || FP.MODTYPE==FP.GENERALISED_MERSENNE |
| { |
| var d=x.pxmul(cc) |
| x.copy(FP.mod(&d)) |
| xes=2 |
| } |
| else { |
| if xes*Int32(cc)<FP.FEXCESS |
| { |
| x.pmul(cc) |
| xes*=Int32(cc); |
| } |
| else { |
| let n=FP(cc) |
| self.mul(n) |
| } |
| } |
| |
| if s {neg(); norm()} |
| |
| } |
| |
| /* this*=this mod Modulus */ |
| mutating func sqr() |
| { |
| if Int64(xes)*Int64(xes) > Int64(FP.FEXCESS) {reduce()} |
| var d=BIG.sqr(x); |
| x.copy(FP.mod(&d)); |
| xes=2 |
| } |
| |
| /* this+=b */ |
| mutating func add(_ b: FP) |
| { |
| x.add(b.x); |
| xes+=b.xes |
| if xes>FP.FEXCESS {reduce()} |
| } |
| /* this-=b */ |
| mutating func sub(_ b: FP) |
| { |
| var n=FP(b) |
| n.neg() |
| self.add(n) |
| } |
| /* this=b-this */ |
| mutating func rsub(_ b: FP) |
| { |
| self.neg(); |
| self.add(b) |
| } |
| /* this/=2 mod Modulus */ |
| mutating func div2() |
| { |
| // x.norm() |
| if (x.parity()==0) |
| {x.fshr(1)} |
| else |
| { |
| x.add(FP.p) |
| x.norm() |
| x.fshr(1) |
| } |
| } |
| /* this=1/this mod Modulus */ |
| |
| mutating func fpow() -> FP |
| { |
| var ac: [Int] = [1, 2, 3, 6, 12, 15, 30, 60, 120, 240, 255] |
| var xp=[FP]() |
| // phase 1 |
| xp.append(FP(self)) |
| xp.append(FP(self)); xp[1].sqr() |
| xp.append(FP(xp[1])); xp[2].mul(self) |
| xp.append(FP(xp[2])); xp[3].sqr() |
| xp.append(FP(xp[3])); xp[4].sqr() |
| xp.append(FP(xp[4])); xp[5].mul(xp[2]) |
| xp.append(FP(xp[5])); xp[6].sqr() |
| xp.append(FP(xp[6])); xp[7].sqr() |
| xp.append(FP(xp[7])); xp[8].sqr() |
| xp.append(FP(xp[8])); xp[9].sqr() |
| xp.append(FP(xp[9])); xp[10].mul(xp[5]) |
| |
| var n: Int |
| var c: Int |
| |
| if (FP.MOD8==5) |
| { |
| n=Int(FP.MODBITS)-3 |
| c=(Int(ROM.MConst)+5)/8 |
| } else { |
| n=Int(FP.MODBITS)-2 |
| c=(Int(ROM.MConst)+3)/4 |
| } |
| |
| |
| var bw=0; var w=1; while w<c {w*=2; bw+=1} |
| var k=w-c |
| |
| var i=10; var key=FP(0) |
| |
| if k != 0 { |
| while ac[i]>k {i-=1} |
| key.copy(xp[i]) |
| k-=ac[i] |
| } |
| while k != 0 { |
| i-=1 |
| 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]) |
| |
| var j=3; var m=8 |
| let nw=n-bw |
| var t=FP(0) |
| |
| while 2*m<nw { |
| t.copy(xp[j]); j+=1 |
| for _ in 0..<m {t.sqr()} |
| xp[j].copy(xp[j-1]) |
| xp[j].mul(t) |
| m*=2 |
| } |
| |
| var lo=nw-m |
| var r=FP(xp[j]) |
| |
| while lo != 0 { |
| m/=2; j-=1 |
| if lo<m {continue} |
| lo-=m |
| t.copy(r) |
| for _ in 0..<m {t.sqr()} |
| r.copy(t) |
| r.mul(xp[j]) |
| } |
| |
| for _ in 0..<bw {r.sqr()} |
| |
| if w-c != 0 { |
| r.mul(key) |
| } |
| return r |
| } |
| |
| mutating func inverse() |
| { |
| if FP.MODTYPE==FP.PSEUDO_MERSENNE { |
| var y=fpow() |
| if (FP.MOD8==5) |
| { |
| var t=FP(self) |
| t.sqr() |
| mul(t) |
| y.sqr() |
| |
| } |
| y.sqr() |
| y.sqr() |
| mul(y) |
| } else { |
| var m2=BIG(ROM.Modulus) |
| m2.dec(2); m2.norm() |
| copy(pow(m2)) |
| } |
| |
| } |
| |
| /* return TRUE if this==a */ |
| func equals(_ a: FP) -> Bool |
| { |
| var f=FP(self) |
| var s=FP(a) |
| f.reduce() |
| s.reduce() |
| if (BIG.comp(f.x,s.x)==0) {return true} |
| return false; |
| } |
| |
| |
| /* return this^e mod Modulus */ |
| mutating func pow(_ e: BIG) -> FP |
| { |
| var tb=[FP]() |
| let n=1+(BIG.NLEN*Int(BIG.BASEBITS)+3)/4 |
| var w=[Int8](repeating: 0,count: n) |
| norm() |
| var t=BIG(e); t.norm() |
| let nb=1+(t.nbits()+3)/4 |
| |
| for i in 0 ..< nb { |
| let lsbs=t.lastbits(4) |
| t.dec(lsbs) |
| t.norm() |
| w[i]=Int8(lsbs) |
| t.fshr(4); |
| } |
| tb.append(FP(1)) |
| tb.append(FP(self)) |
| for i in 2 ..< 16 { |
| tb.append(FP(tb[i-1])) |
| tb[i].mul(self) |
| } |
| var r=FP(tb[Int(w[nb-1])]) |
| for i in (0...nb-2).reversed() { |
| r.sqr() |
| r.sqr() |
| r.sqr() |
| r.sqr() |
| r.mul(tb[Int(w[i])]) |
| } |
| r.reduce() |
| return r |
| } |
| |
| |
| /* return this^e mod Modulus |
| func pow(_ e: BIG) -> FP |
| { |
| let r=FP(1) |
| e.norm() |
| x.norm() |
| let m=FP(self) |
| while (true) |
| { |
| let bt=e.parity() |
| e.fshr(1) |
| if bt==1 {r.mul(m)} |
| if e.iszilch() {break} |
| m.sqr(); |
| } |
| r.x.mod(FP.p); |
| return r; |
| } */ |
| |
| /* return sqrt(this) mod Modulus */ |
| mutating func sqrt() -> FP |
| { |
| reduce(); |
| if (FP.MOD8==5) |
| { |
| var v: FP |
| var i=FP(self); i.x.shl(1) |
| if FP.MODTYPE==FP.PSEUDO_MERSENNE { |
| v=i.fpow() |
| } else { |
| var b=BIG(FP.p) |
| b.dec(5); b.norm(); b.shr(3) |
| v=i.pow(b) |
| } |
| i.mul(v); i.mul(v) |
| i.x.dec(1) |
| var r=FP(self) |
| r.mul(v); r.mul(i) |
| r.reduce() |
| return r |
| } |
| else |
| { |
| if FP.MODTYPE==FP.PSEUDO_MERSENNE { |
| var r=fpow() |
| r.mul(self) |
| return r |
| } else { |
| var b=BIG(FP.p) |
| b.inc(1); b.norm(); b.shr(2) |
| return pow(b) |
| } |
| } |
| } |
| /* return jacobi symbol (this/Modulus) */ |
| func jacobi() -> Int |
| { |
| var w=redc() |
| return w.jacobi(FP.p) |
| } |
| |
| } |
