| /* |
| 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. |
| */ |
| |
| // |
| // big.swift |
| // |
| // Created by Michael Scott on 12/06/2015. |
| // Copyright (c) 2015 Michael Scott. All rights reserved. |
| // BIG number class |
| // |
| |
| import amcl |
| |
| //#if D32 |
| //public typealias Chunk = Int32 |
| //public typealias DChunk = Int64 |
| //#endif |
| |
| //#if D64 |
| //public typealias Chunk = Int64 |
| //#endif |
| |
| |
| public struct BIG{ |
| //#if D32 |
| // static public let CHUNK:Int=32 |
| // static let BASEBITS:UInt = @BASE32@ |
| //#endif |
| //#if D64 |
| // static public let CHUNK:Int=64 |
| // static let BASEBITS:UInt = @BASE64@ |
| //#endif |
| |
| // static let MODBYTES:UInt = @NB@ |
| |
| |
| |
| var w=[Chunk](repeating: 0,count: CONFIG_BIG.NLEN) |
| /* Constructors */ |
| init() { |
| for i in 0 ..< CONFIG_BIG.NLEN {w[i]=0} |
| } |
| init(_ x: Int) |
| { |
| w[0]=Chunk(x); |
| for i in 1 ..< CONFIG_BIG.NLEN {w[i]=0} |
| } |
| init(_ x: BIG) |
| { |
| for i in 0 ..< CONFIG_BIG.NLEN {w[i]=x.w[i]} |
| } |
| init(_ x: DBIG) |
| { |
| for i in 0 ..< CONFIG_BIG.NLEN {w[i]=x.w[i]} |
| } |
| public init(_ x: [Chunk]) |
| { |
| for i in 0 ..< CONFIG_BIG.NLEN {w[i]=x[i]} |
| } |
| func get(_ i: Int) -> Chunk |
| { |
| return w[i] |
| } |
| mutating func set(_ i: Int,_ x: Chunk) |
| { |
| w[i]=x |
| } |
| mutating func xortop(_ x: Chunk) |
| { |
| w[CONFIG_BIG.NLEN-1]^=x |
| } |
| mutating func ortop(_ x: Chunk) |
| { |
| w[CONFIG_BIG.NLEN-1]|=x |
| } |
| |
| #if D32 |
| |
| static func muladd(_ a: Chunk,_ b: Chunk,_ c: Chunk,_ r: Chunk) -> (Chunk,Chunk) |
| { |
| let prod:DChunk = DChunk(a)*DChunk(b)+DChunk(c)+DChunk(r) |
| let bot=Chunk(prod&DChunk(CONFIG_BIG.BMASK)) |
| let top=Chunk(prod>>DChunk(CONFIG_BIG.BASEBITS)) |
| return (top,bot) |
| } |
| #endif |
| #if D64 |
| |
| static func muladd(_ a: Chunk,_ b: Chunk,_ c: Chunk,_ r: Chunk) -> (Chunk,Chunk) |
| { |
| let (tp,bt)=a.multipliedFullWidth(by: b) |
| var bot = Chunk(bt)&CONFIG_BIG.BMASK |
| var top = (tp << Chunk(64-CONFIG_BIG.BASEBITS)) | Chunk(bt >> CONFIG_BIG.BASEBITS) |
| |
| bot+=c; bot+=r |
| let carry=bot>>Chunk(CONFIG_BIG.BASEBITS) |
| bot &= CONFIG_BIG.BMASK |
| top+=carry |
| return (top,bot) |
| } |
| |
| #endif |
| /* test for zero */ |
| func iszilch() -> Bool |
| { |
| for i in 0 ..< CONFIG_BIG.NLEN {if w[i] != 0 {return false}} |
| return true |
| } |
| /* set to zero */ |
| mutating func zero() |
| { |
| for i in 0 ..< CONFIG_BIG.NLEN {w[i] = 0} |
| } |
| /* set to one */ |
| mutating func one() |
| { |
| w[0]=1 |
| for i in 1 ..< CONFIG_BIG.NLEN {w[i]=0} |
| } |
| /* Test for equal to one */ |
| func isunity() -> Bool |
| { |
| for i in 1 ..< CONFIG_BIG.NLEN {if w[i] != 0 {return false}} |
| if w[0] != 1 {return false} |
| return true |
| } |
| /* Copy from another BIG */ |
| mutating func copy(_ x: BIG) |
| { |
| for i in 0 ..< CONFIG_BIG.NLEN {w[i] = x.w[i]} |
| } |
| mutating func copy(_ x: DBIG) |
| { |
| for i in 0 ..< CONFIG_BIG.NLEN {w[i] = x.w[i]} |
| } |
| /* Conditional swap of two bigs depending on d using XOR - no branches */ |
| mutating func cswap(_ b: inout BIG,_ d: Int) |
| { |
| var c = Chunk(d) |
| c = ~(c-1) |
| for i in 0 ..< CONFIG_BIG.NLEN |
| { |
| let t=c&(w[i]^b.w[i]) |
| w[i]^=t |
| b.w[i]^=t |
| } |
| } |
| mutating func cmove(_ g: BIG,_ d: Int) |
| { |
| let b=Chunk(-d) |
| for i in 0 ..< CONFIG_BIG.NLEN |
| { |
| w[i]^=(w[i]^g.w[i])&b; |
| } |
| } |
| /* normalise BIG - force all digits < 2^CONFIG_BIG.BASEBITS */ |
| @discardableResult mutating func norm() -> Chunk |
| { |
| var carry=Chunk(0); |
| for i in 0 ..< CONFIG_BIG.NLEN-1 |
| { |
| let d=w[i]+carry |
| w[i]=d&CONFIG_BIG.BMASK |
| carry=d>>Chunk(CONFIG_BIG.BASEBITS) |
| } |
| w[CONFIG_BIG.NLEN-1]+=carry |
| return (w[CONFIG_BIG.NLEN-1]>>Chunk((8*CONFIG_BIG.MODBYTES)%CONFIG_BIG.BASEBITS)) |
| } |
| /* Shift right by less than a word */ |
| @discardableResult mutating func fshr(_ k: UInt) -> Int |
| { |
| let kw=Chunk(k); |
| let r=w[0]&((Chunk(1)<<kw)-1) |
| for i in 0 ..< CONFIG_BIG.NLEN-1 |
| { |
| w[i]=(w[i]>>kw)|((w[i+1]<<(Chunk(CONFIG_BIG.BASEBITS)-kw))&CONFIG_BIG.BMASK) |
| } |
| w[CONFIG_BIG.NLEN-1]>>=kw; |
| return Int(r) |
| } |
| /* general shift right */ |
| mutating func shr(_ k: UInt) |
| { |
| let n=k%CONFIG_BIG.BASEBITS |
| let m=Int(k/CONFIG_BIG.BASEBITS) |
| for i in 0 ..< CONFIG_BIG.NLEN-m-1 |
| { |
| w[i]=(w[m+i]>>Chunk(n))|((w[m+i+1]<<Chunk(CONFIG_BIG.BASEBITS-n))&CONFIG_BIG.BMASK) |
| } |
| w[CONFIG_BIG.NLEN - m - 1]=w[CONFIG_BIG.NLEN-1]>>Chunk(n) |
| for i in CONFIG_BIG.NLEN - m ..< CONFIG_BIG.NLEN {w[i]=0} |
| } |
| /* Shift right by less than a word */ |
| @discardableResult mutating func fshl(_ k: Int) -> Int |
| { |
| let kw=Chunk(k) |
| w[CONFIG_BIG.NLEN-1]=((w[CONFIG_BIG.NLEN-1]<<kw))|(w[CONFIG_BIG.NLEN-2]>>(Chunk(CONFIG_BIG.BASEBITS)-kw)) |
| for i in (1...CONFIG_BIG.NLEN-2).reversed() |
| { |
| w[i]=((w[i]<<kw)&CONFIG_BIG.BMASK)|(w[i-1]>>(Chunk(CONFIG_BIG.BASEBITS)-kw)) |
| } |
| w[0]=(w[0]<<kw)&CONFIG_BIG.BMASK |
| return Int(w[CONFIG_BIG.NLEN-1]>>Chunk((8*CONFIG_BIG.MODBYTES)%CONFIG_BIG.BASEBITS)) |
| } |
| /* general shift left */ |
| mutating func shl(_ k: UInt) |
| { |
| let n=k%CONFIG_BIG.BASEBITS |
| let m=Int(k/CONFIG_BIG.BASEBITS) |
| |
| w[CONFIG_BIG.NLEN-1]=(w[CONFIG_BIG.NLEN-1-m]<<Chunk(n)) |
| if CONFIG_BIG.NLEN>=m+2 {w[CONFIG_BIG.NLEN-1]|=(w[CONFIG_BIG.NLEN-m-2]>>Chunk(CONFIG_BIG.BASEBITS-n))} |
| for i in (m+1...CONFIG_BIG.NLEN-2).reversed() |
| { |
| w[i]=((w[i-m]<<Chunk(n))&CONFIG_BIG.BMASK)|(w[i-m-1]>>Chunk(CONFIG_BIG.BASEBITS-n)) |
| } |
| w[m]=(w[0]<<Chunk(n))&CONFIG_BIG.BMASK |
| for i in 0 ..< m {w[i]=0} |
| } |
| /* return number of bits */ |
| func nbits() -> Int |
| { |
| var k=(CONFIG_BIG.NLEN-1) |
| var t=BIG(self) |
| t.norm() |
| while k>=0 && t.w[k]==0 {k -= 1} |
| if k<0 {return 0} |
| var bts=Int(CONFIG_BIG.BASEBITS)*k |
| var c=t.w[k]; |
| while c != 0 {c/=2; bts += 1} |
| return bts |
| } |
| func toRawString() -> String |
| { |
| var s:String="(" |
| for i in 0 ..< CONFIG_BIG.NLEN-1 |
| { |
| let n=String(w[i],radix:16,uppercase:false) |
| s+=n |
| s+="," |
| |
| } |
| let n=String(w[CONFIG_BIG.NLEN-1],radix:16,uppercase:false) |
| s+=n |
| s+=")" |
| return s |
| } |
| /* Convert to Hex String */ |
| func toString() -> String |
| { |
| _ = BIG() |
| var s:String="" |
| var len=nbits() |
| if len%4 == 0 {len/=4} |
| else {len/=4; len += 1} |
| if len<2*Int(CONFIG_BIG.MODBYTES) {len=2*Int(CONFIG_BIG.MODBYTES)} |
| |
| for i in (0...len-1).reversed() |
| { |
| var b = BIG(self) |
| b.shr(UInt(i*4)) |
| let n=String(b.w[0]&15,radix:16,uppercase:false) |
| s+=n |
| } |
| |
| return s |
| } |
| /* return this+x */ |
| func plus(_ x: BIG) -> BIG |
| { |
| var s=BIG() |
| for i in 0 ..< CONFIG_BIG.NLEN |
| { |
| s.w[i]=w[i]+x.w[i] |
| } |
| return s |
| } |
| /* this+=x */ |
| mutating func add(_ x: BIG) |
| { |
| for i in 0 ..< CONFIG_BIG.NLEN |
| { |
| w[i]+=x.w[i] |
| } |
| } |
| |
| /* this|=x */ |
| mutating func or(_ x: BIG) |
| { |
| for i in 0 ..< CONFIG_BIG.NLEN |
| { |
| w[i]|=x.w[i] |
| } |
| } |
| |
| /* this+=x, where x is int */ |
| mutating func inc(_ x: Int) { |
| norm(); |
| w[0]+=Chunk(x); |
| } |
| /* return this.x */ |
| func minus(_ x: BIG) -> BIG |
| { |
| var d=BIG(); |
| for i in 0 ..< CONFIG_BIG.NLEN |
| { |
| d.w[i]=w[i]-x.w[i]; |
| } |
| return d; |
| } |
| /* this-=x */ |
| mutating func sub(_ x: BIG) |
| { |
| for i in 0 ..< CONFIG_BIG.NLEN |
| { |
| w[i]-=x.w[i] |
| } |
| } |
| /* reverse subtract this=x-this */ |
| mutating func rsub(_ x: BIG) |
| { |
| for i in 0 ..< CONFIG_BIG.NLEN |
| { |
| w[i]=x.w[i]-w[i] |
| } |
| } |
| /* this-=x where x is int */ |
| mutating func dec(_ x: Int) { |
| norm(); |
| w[0]-=Chunk(x); |
| } |
| /* this*=x, where x is small int<NEXCESS */ |
| mutating func imul(_ c: Int) |
| { |
| for i in 0 ..< CONFIG_BIG.NLEN {w[i]*=Chunk(c)} |
| } |
| /* convert this BIG to byte array */ |
| func tobytearray(_ b: inout [UInt8],_ n: Int) |
| { |
| //norm(); |
| var c=BIG(self); |
| c.norm() |
| for i in (0...Int(CONFIG_BIG.MODBYTES)-1).reversed() |
| { |
| b[i+n]=UInt8(c.w[0]&0xff); |
| c.fshr(8); |
| } |
| } |
| /* convert from byte array to BIG */ |
| static func frombytearray(_ b: [UInt8],_ n: Int) -> BIG |
| { |
| var m=BIG(); |
| |
| for i in 0 ..< Int(CONFIG_BIG.MODBYTES) |
| { |
| m.fshl(8) |
| m.w[0]+=Chunk(b[i+n])&0xff |
| } |
| return m; |
| } |
| func toBytes(_ b: inout [UInt8]) |
| { |
| tobytearray(&b,0) |
| } |
| static func fromBytes(_ b: [UInt8]) -> BIG |
| { |
| return frombytearray(b,0) |
| } |
| |
| /* this*=x, where x is >NEXCESS */ |
| @discardableResult mutating func pmul(_ c: Int) -> Chunk |
| { |
| var carry=Chunk(0); |
| //norm(); |
| for i in 0 ..< CONFIG_BIG.NLEN |
| { |
| let ak=w[i] |
| let (top,bot)=BIG.muladd(ak,Chunk(c),carry,Chunk(0)) |
| carry=top; w[i]=bot; |
| } |
| return carry; |
| } |
| /* this*=c and catch overflow in DBIG */ |
| mutating func pxmul(_ c: Int) -> DBIG |
| { |
| var m=DBIG() |
| var carry=Chunk(0) |
| for j in 0 ..< CONFIG_BIG.NLEN |
| { |
| let (top,bot)=BIG.muladd(w[j],Chunk(c),carry,m.w[j]) |
| carry=top; m.w[j]=bot |
| } |
| m.w[CONFIG_BIG.NLEN]=carry |
| return m; |
| } |
| /* divide by 3 */ |
| mutating func div3() -> Chunk |
| { |
| var carry=Chunk(0) |
| norm(); |
| let base=Chunk(1<<CONFIG_BIG.BASEBITS); |
| for i in (0...CONFIG_BIG.NLEN-1).reversed() |
| { |
| let ak=(carry*base+w[i]); |
| w[i]=ak/3; |
| carry=ak%3; |
| } |
| return carry; |
| } |
| /* return a*b where result fits in a BIG */ |
| static func smul(_ a: BIG,_ b: BIG) -> BIG |
| { |
| var c=BIG() |
| for i in 0 ..< CONFIG_BIG.NLEN |
| { |
| var carry=Chunk(0) |
| for j in 0 ..< CONFIG_BIG.NLEN |
| { |
| if (i+j<CONFIG_BIG.NLEN) { |
| let (top,bot)=BIG.muladd(a.w[i],b.w[j],carry,c.w[i+j]) |
| carry=top; c.w[i+j]=bot |
| } |
| } |
| } |
| return c; |
| } |
| /* Compare a and b, return 0 if a==b, -1 if a<b, +1 if a>b. Inputs must be normalised */ |
| static func comp(_ a: BIG,_ b: BIG) -> Int |
| { |
| for i in (0...CONFIG_BIG.NLEN-1).reversed() |
| { |
| 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 */ |
| mutating func mod2m(_ m: UInt) |
| { |
| let wd=Int(m/CONFIG_BIG.BASEBITS) |
| let bt=m%CONFIG_BIG.BASEBITS |
| let msk=Chunk(1<<bt)-1; |
| w[wd]&=msk; |
| for i in wd+1 ..< CONFIG_BIG.NLEN {w[i]=0} |
| } |
| /* Arazi and Qi inversion mod 256 */ |
| static func invmod256(_ a: Int) -> Int |
| { |
| var t1:Int=0 |
| var c=(a>>1)&1 |
| t1+=c |
| t1&=1 |
| t1=2-t1 |
| t1<<=1 |
| var U=t1+1 |
| |
| // i=2 |
| var b=a&3 |
| t1=U*b; t1>>=2 |
| c=(a>>2)&3 |
| var 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 |
| } |
| /* return parity */ |
| func parity() -> Int |
| { |
| return Int(w[0]%2) |
| } |
| |
| /* return n-th bit */ |
| func bit(_ n: UInt) -> Int |
| { |
| if ((w[Int(n/CONFIG_BIG.BASEBITS)]&(1<<Chunk(n%CONFIG_BIG.BASEBITS)))>0) {return 1;} |
| else {return 0;} |
| } |
| |
| /* return n last bits */ |
| mutating func lastbits(_ n: UInt) -> Int |
| { |
| let msk=(Chunk(1)<<Chunk(n))-1; |
| norm(); |
| return Int((w[0])&msk) |
| } |
| /* a=1/a mod 2^256. This is very fast! */ |
| mutating func invmod2m() |
| { |
| var U=BIG() |
| var b=BIG() |
| var c=BIG() |
| |
| U.inc(BIG.invmod256(lastbits(8))) |
| |
| var i=UInt(8) |
| while (i<CONFIG_BIG.BIGBITS) |
| { |
| U.norm(); |
| b.copy(self) |
| b.mod2m(i) |
| var t1=BIG.smul(U,b) |
| t1.shr(i) |
| c.copy(self) |
| c.shr(i) |
| c.mod2m(i) |
| |
| var t2=BIG.smul(U,c) |
| t2.mod2m(i) |
| t1.add(t2); t1.norm() |
| 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) |
| i<<=1 |
| } |
| U.mod2m(CONFIG_BIG.BIGBITS) |
| self.copy(U) |
| self.norm() |
| } |
| /* reduce this mod m */ |
| mutating func mod(_ m1: BIG) |
| { |
| var k=0 |
| var m=BIG(m1) |
| var r=BIG(0) |
| norm() |
| if (BIG.comp(self,m)<0) {return} |
| repeat |
| { |
| m.fshl(1) |
| k += 1 |
| } while (BIG.comp(self,m)>=0) |
| |
| while (k>0) |
| { |
| m.fshr(1) |
| |
| r.copy(self) |
| r.sub(m) |
| r.norm() |
| cmove(r,Int(1-((r.w[CONFIG_BIG.NLEN-1]>>Chunk(CONFIG_BIG.CHUNK-1))&1))) |
| |
| k -= 1 |
| } |
| } |
| /* divide this by m */ |
| mutating func div(_ m1: BIG) |
| { |
| var k=0 |
| norm() |
| var e=BIG(1) |
| var b=BIG(self) |
| var r=BIG(0) |
| var m=BIG(m1) |
| zero() |
| |
| while (BIG.comp(b,m)>=0) |
| { |
| e.fshl(1) |
| m.fshl(1) |
| k += 1 |
| } |
| |
| while (k>0) |
| { |
| m.fshr(1) |
| e.fshr(1) |
| |
| r.copy(b) |
| r.sub(m) |
| r.norm() |
| let d=Int(1-((r.w[CONFIG_BIG.NLEN-1]>>Chunk(CONFIG_BIG.CHUNK-1))&1)) |
| b.cmove(r,d) |
| r.copy(self) |
| r.add(e) |
| r.norm() |
| cmove(r,d) |
| |
| k -= 1 |
| } |
| } |
| /* get 8*CONFIG_BIG.MODBYTES size random number */ |
| static func random(_ rng: inout RAND) -> BIG |
| { |
| var m=BIG(); |
| var j:Int=0 |
| var r:UInt8=0 |
| /* generate random BIG */ |
| for _ in 0 ..< Int(8*CONFIG_BIG.MODBYTES) |
| { |
| if (j==0) {r=rng.getByte()} |
| else {r>>=1} |
| |
| let b=Chunk(r&1) |
| m.shl(1); m.w[0]+=b |
| j += 1; j&=7 |
| } |
| return m |
| } |
| |
| /* Create random BIG in portable way, one bit at a time, less than q */ |
| static public func randomnum(_ q: BIG,_ rng: inout RAND) -> BIG |
| { |
| var d=DBIG(0); |
| var j:Int=0 |
| var r:UInt8=0 |
| |
| for _ in 0 ..< 2*q.nbits() |
| { |
| if (j==0) {r=rng.getByte()} |
| else {r>>=1} |
| |
| let b=Chunk(r&1) |
| d.shl(1); d.w[0]+=b |
| j += 1; j&=7 |
| } |
| let m=d.mod(q) |
| return m |
| } |
| |
| /* Jacobi Symbol (this/p). Returns 0, 1 or -1 */ |
| mutating func jacobi(_ p: BIG) -> Int |
| { |
| var n8:Int |
| var k:Int |
| var m:Int=0; |
| var t=BIG() |
| var x=BIG() |
| var n=BIG() |
| let zilch=BIG() |
| let one=BIG(1) |
| if (p.parity()==0 || BIG.comp(self,zilch)==0 || BIG.comp(p,one)<=0) {return 0} |
| norm() |
| x.copy(self) |
| n.copy(p) |
| x.mod(p) |
| |
| while (BIG.comp(n,one)>0) |
| { |
| if (BIG.comp(x,zilch)==0) {return 0} |
| n8=n.lastbits(3) |
| k=0 |
| while (x.parity()==0) |
| { |
| k += 1 |
| x.shr(1) |
| } |
| if (k%2==1) {m+=((n8*n8-1)/8)} |
| let w=Int(x.lastbits(2)-1) |
| m+=(n8-1)*w/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 */ |
| mutating func invmodp(_ p: BIG) |
| { |
| mod(p) |
| var u=BIG(self) |
| var v=BIG(p) |
| var x1=BIG(1) |
| var x2=BIG() |
| var t=BIG() |
| let one=BIG(1) |
| |
| while ((BIG.comp(u,one) != 0 ) && (BIG.comp(v,one) != 0 )) |
| { |
| while (u.parity()==0) |
| { |
| u.fshr(1); |
| if (x1.parity() != 0 ) |
| { |
| x1.add(p); |
| x1.norm(); |
| } |
| x1.fshr(1); |
| } |
| while (v.parity()==0) |
| { |
| v.fshr(1); |
| if (x2.parity() != 0 ) |
| { |
| x2.add(p); |
| x2.norm(); |
| } |
| x2.fshr(1); |
| } |
| if (BIG.comp(u,v)>=0) |
| { |
| u.sub(v); |
| u.norm(); |
| if (BIG.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 (BIG.comp(x2,x1)>=0) {x2.sub(x1)} |
| else |
| { |
| t.copy(p); |
| t.sub(x1); |
| x2.add(t); |
| } |
| x2.norm(); |
| } |
| } |
| if (BIG.comp(u,one)==0) {copy(x1)} |
| else {copy(x2)} |
| } |
| /* return a*b as DBIG */ |
| #if D32 |
| static func mul(_ a: BIG,_ b:BIG) -> DBIG |
| { |
| var t:DChunk |
| var co:DChunk |
| var c=DBIG() |
| let RM:DChunk=DChunk(CONFIG_BIG.BMASK); |
| let RB:DChunk=DChunk(CONFIG_BIG.BASEBITS) |
| |
| var d=[DChunk](repeating: 0,count: CONFIG_BIG.NLEN) |
| var s:DChunk |
| for i in 0 ..< CONFIG_BIG.NLEN |
| { |
| d[i]=DChunk(a.w[i])*DChunk(b.w[i]); |
| } |
| s=d[0] |
| t=s; c.w[0]=Chunk(t&RM); co=t>>RB |
| for k in 1 ..< CONFIG_BIG.NLEN |
| { |
| s+=d[k]; t=co+s; |
| for i in 1+k/2...k |
| {t+=DChunk(a.w[i]-a.w[k-i])*DChunk(b.w[k-i]-b.w[i])} |
| c.w[k]=Chunk(t&RM); co=t>>RB |
| } |
| for k in CONFIG_BIG.NLEN ..< 2*CONFIG_BIG.NLEN-1 |
| { |
| s-=d[k-CONFIG_BIG.NLEN]; t=co+s; |
| |
| var i=1+k/2 |
| while i<CONFIG_BIG.NLEN |
| { |
| t+=DChunk(a.w[i]-a.w[k-i])*DChunk(b.w[k-i]-b.w[i]) |
| i+=1 |
| } |
| |
| c.w[k]=Chunk(t&RM); co=t>>RB |
| } |
| c.w[2*CONFIG_BIG.NLEN-1]=Chunk(co); |
| |
| return c |
| } |
| |
| /* return a^2 as DBIG */ |
| static func sqr(_ a: BIG) -> DBIG |
| { |
| var t:DChunk |
| var co:DChunk |
| var c=DBIG() |
| let RM:DChunk=DChunk(CONFIG_BIG.BMASK); |
| let RB:DChunk=DChunk(CONFIG_BIG.BASEBITS) |
| |
| t=DChunk(a.w[0])*DChunk(a.w[0]) |
| c.w[0]=Chunk(t&RM); co=t>>RB |
| var j:Int |
| j=1 |
| while j<CONFIG_BIG.NLEN-1 |
| { |
| t=DChunk(a.w[j])*DChunk(a.w[0]); for i in 1 ..< (j+1)/2 {t+=DChunk(a.w[j-i])*DChunk(a.w[i])}; t+=t; t+=co |
| c.w[j]=Chunk(t&RM); co=t>>RB |
| j+=1 |
| t=DChunk(a.w[j])*DChunk(a.w[0]); for i in 1 ..< (j+1)/2 {t+=DChunk(a.w[j-i])*DChunk(a.w[i])}; t+=t; t+=co; t+=DChunk(a.w[j/2])*DChunk(a.w[j/2]) |
| c.w[j]=Chunk(t&RM); co=t>>RB |
| j+=1 |
| } |
| |
| j=CONFIG_BIG.NLEN-1+(CONFIG_BIG.NLEN%2) |
| while j<CONFIG_BIG.DNLEN-3 |
| { |
| t=DChunk(a.w[CONFIG_BIG.NLEN-1])*DChunk(a.w[j-CONFIG_BIG.NLEN+1]); for i in j-CONFIG_BIG.NLEN+2 ..< (j+1)/2 {t+=DChunk(a.w[j-i])*DChunk(a.w[i])}; t+=t; t+=co |
| c.w[j]=Chunk(t&RM); co=t>>RB |
| j+=1; |
| t=DChunk(a.w[CONFIG_BIG.NLEN-1])*DChunk(a.w[j-CONFIG_BIG.NLEN+1]); for i in j-CONFIG_BIG.NLEN+2 ..< (j+1)/2 {t+=DChunk(a.w[j-i])*DChunk(a.w[i])}; t+=t; t+=co; t+=DChunk(a.w[j/2])*DChunk(a.w[j/2]) |
| c.w[j]=Chunk(t&RM); co=t>>RB |
| j+=1; |
| } |
| |
| t=DChunk(a.w[CONFIG_BIG.NLEN-2])*DChunk(a.w[CONFIG_BIG.NLEN-1]) |
| t+=t; t+=co; |
| c.w[CONFIG_BIG.DNLEN-3]=Chunk(t&RM); co=t>>RB |
| |
| t=DChunk(a.w[CONFIG_BIG.NLEN-1])*DChunk(a.w[CONFIG_BIG.NLEN-1])+co |
| c.w[CONFIG_BIG.DNLEN-2]=Chunk(t&RM); co=t>>RB |
| c.w[CONFIG_BIG.DNLEN-1]=Chunk(co) |
| |
| return c |
| } |
| static func monty(_ md:BIG,_ mc:Chunk,_ d: inout DBIG) -> BIG |
| { |
| let RM:DChunk=DChunk(CONFIG_BIG.BMASK) |
| let RB:DChunk=DChunk(CONFIG_BIG.BASEBITS) |
| |
| |
| var t:DChunk |
| var s:DChunk |
| var c:DChunk |
| var dd=[DChunk](repeating: 0,count: CONFIG_BIG.NLEN) |
| var v=[Chunk](repeating: 0,count: CONFIG_BIG.NLEN) |
| var b=BIG(0) |
| |
| t=DChunk(d.w[0]); v[0]=(Chunk(t&RM)&*mc)&CONFIG_BIG.BMASK; t+=DChunk(v[0])*DChunk(md.w[0]); c=DChunk(d.w[1])+(t>>RB); s=0 |
| for k in 1 ..< CONFIG_BIG.NLEN |
| { |
| t=c+s+DChunk(v[0])*DChunk(md.w[k]) |
| var i=1+k/2 |
| while i<k |
| { |
| t+=DChunk(v[k-i]-v[i])*DChunk(md.w[i]-md.w[k-i]) |
| i+=1 |
| } |
| v[k]=(Chunk(t&RM)&*mc)&CONFIG_BIG.BMASK; t+=DChunk(v[k])*DChunk(md.w[0]); c=DChunk(d.w[k+1])+(t>>RB) |
| dd[k]=DChunk(v[k])*DChunk(md.w[k]); s+=dd[k] |
| } |
| for k in CONFIG_BIG.NLEN ..< 2*CONFIG_BIG.NLEN-1 |
| { |
| t=c+s |
| var i=1+k/2 |
| while i<CONFIG_BIG.NLEN |
| { |
| t+=DChunk(v[k-i]-v[i])*DChunk(md.w[i]-md.w[k-i]) |
| i+=1 |
| } |
| b.w[k-CONFIG_BIG.NLEN]=Chunk(t&RM); c=DChunk(d.w[k+1])+(t>>RB); s-=dd[k-CONFIG_BIG.NLEN+1] |
| } |
| b.w[CONFIG_BIG.NLEN-1]=Chunk(c&RM) |
| return b; |
| } |
| #endif |
| #if D64 |
| static func mul(_ a: BIG,_ b:BIG) -> DBIG |
| { |
| var c=DBIG() |
| var carry:Chunk |
| for i in 0 ..< CONFIG_BIG.NLEN { |
| carry=0 |
| for j in 0..<CONFIG_BIG.NLEN { |
| let (top,bot)=BIG.muladd(a.w[i],b.w[j],carry,c.w[i+j]) |
| carry=top; c.w[i+j]=bot |
| } |
| c.w[CONFIG_BIG.NLEN+i]=carry |
| } |
| return c |
| } |
| static func sqr(_ a: BIG) -> DBIG |
| { |
| var c=DBIG() |
| var carry:Chunk |
| for i in 0 ..< CONFIG_BIG.NLEN { |
| carry=0 |
| for j in i+1 ..< CONFIG_BIG.NLEN { |
| let (top,bot)=BIG.muladd(2*a.w[i],a.w[j],carry,c.w[i+j]) |
| carry=top; c.w[i+j]=bot |
| } |
| c.w[CONFIG_BIG.NLEN+i]=carry |
| } |
| for i in 0 ..< CONFIG_BIG.NLEN { |
| let (top,bot)=BIG.muladd(a.w[i],a.w[i],Chunk(0),c.w[2*i]) |
| c.w[2*i]=bot |
| c.w[2*i+1]+=top |
| } |
| c.norm() |
| return c |
| } |
| static func monty(_ md:BIG,_ mc:Chunk,_ d: inout DBIG) -> BIG |
| { |
| var b=BIG() |
| var carry:Chunk |
| var m:Chunk |
| for i in 0 ..< CONFIG_BIG.NLEN { |
| if mc == -1 { |
| m=(-d.w[i])&CONFIG_BIG.BMASK |
| } else { |
| if mc == 1 { |
| m=d.w[i] |
| } else { |
| m=(mc&*d.w[i])&CONFIG_BIG.BMASK; |
| } |
| } |
| carry=0 |
| for j in 0 ..< CONFIG_BIG.NLEN { |
| let (top,bot)=BIG.muladd(m,md.w[j],carry,d.w[i+j]) |
| carry=top; d.w[i+j]=bot |
| } |
| d.w[CONFIG_BIG.NLEN+i]+=carry |
| } |
| for i in 0 ..< CONFIG_BIG.NLEN { |
| b.w[i]=d.w[CONFIG_BIG.NLEN+i] |
| } |
| b.norm(); |
| return b |
| } |
| #endif |
| |
| /* Optimized combined shift, subtract and norm */ |
| static func ssn(_ r: inout BIG,_ a :BIG,_ m: inout BIG) -> Int |
| { |
| let n=CONFIG_BIG.NLEN-1 |
| m.w[0]=(m.w[0]>>1)|((m.w[1]<<Chunk(CONFIG_BIG.BASEBITS-1))&CONFIG_BIG.BMASK) |
| r.w[0]=a.w[0]-m.w[0] |
| var carry=r.w[0]>>Chunk(CONFIG_BIG.BASEBITS) |
| r.w[0] &= CONFIG_BIG.BMASK |
| for i in 1 ..< n { |
| m.w[i]=(m.w[i]>>1)|((m.w[i+1]<<Chunk(CONFIG_BIG.BASEBITS-1))&CONFIG_BIG.BMASK) |
| r.w[i]=a.w[i]-m.w[i]+carry |
| carry=r.w[i]>>Chunk(CONFIG_BIG.BASEBITS) |
| r.w[i] &= CONFIG_BIG.BMASK |
| } |
| m.w[n]>>=1 |
| r.w[n]=a.w[n]-m.w[n]+carry |
| return Int((r.w[n]>>Chunk(CONFIG_BIG.CHUNK-1))&Chunk(1)) |
| } |
| |
| /* return a*b mod m */ |
| static func modmul(_ a1: BIG,_ b1 :BIG,_ m: BIG) -> BIG |
| { |
| var a=BIG(a1); var b=BIG(b1); |
| a.mod(m) |
| b.mod(m) |
| var d=mul(a,b) |
| return d.mod(m) |
| } |
| |
| /* return a^2 mod m */ |
| static func modsqr(_ a1: BIG,_ m: BIG) -> BIG |
| { |
| var a=BIG(a1) |
| a.mod(m) |
| var d=sqr(a) |
| return d.mod(m) |
| } |
| |
| /* return -a mod m */ |
| static func modneg(_ a1: BIG,_ m: BIG) -> BIG |
| { |
| var a=BIG(a1) |
| a.mod(m) |
| return m.minus(a) |
| } |
| |
| /* return this^e mod m */ |
| mutating func powmod(_ e1: BIG,_ m: BIG) -> BIG |
| { |
| norm(); |
| var e=BIG(e1) |
| e.norm(); |
| var a=BIG(1) |
| var z=BIG(e) |
| var s=BIG(self) |
| while (true) |
| { |
| let bt=z.parity(); |
| z.fshr(1) |
| if bt==1 {a=BIG.modmul(a,s,m)} |
| if (z.iszilch()) {break} |
| s=BIG.modsqr(s,m) |
| } |
| return a |
| } |
| } |