version3/swift/big.swift - incubator-milagro-crypto - Git at Google

 /*
 	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
     }
 }
	/*
	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<2Int(CONFIG_BIG.MODBYTES) {len=2Int(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 ab 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 8CONFIG_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 ab 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 ab 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
	}
	}