/*
	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@


    static let NLEN:Int=Int(1+((8*BIG.MODBYTES-1)/BIG.BASEBITS))
    static let DNLEN:Int=2*BIG.NLEN
    static let BMASK:Chunk=((1<<Chunk(BIG.BASEBITS))-1)
    static let HBITS = (BIG.BASEBITS/2)
    static let HMASK:Chunk = ((1<<Chunk(BIG.HBITS))-1) 
    static let NEXCESS:Int = (1<<(BIG.CHUNK-Int(BIG.BASEBITS)-1))
    static let BIGBITS:UInt = (BIG.MODBYTES*8)

    var w=[Chunk](repeating: 0,count: NLEN)
/* Constructors */
    init() {
        for i in 0 ..< BIG.NLEN {w[i]=0}
    }
    init(_ x: Int)
    {
        w[0]=Chunk(x);
        for i in 1 ..< BIG.NLEN {w[i]=0}
    }
    init(_ x: BIG)
    {
        for i in 0 ..< BIG.NLEN {w[i]=x.w[i]}
    }
    init(_ x: DBIG)
    {
        for i in 0 ..< BIG.NLEN {w[i]=x.w[i]}
    }
    public init(_ x: [Chunk])
    {
        for i in 0 ..< 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[BIG.NLEN-1]^=x
    }
    mutating func ortop(_ x: Chunk)
    {
        w[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(BIG.BMASK))
        let top=Chunk(prod>>DChunk(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)&BIG.BMASK
	var top = (tp << Chunk(64-BIG.BASEBITS)) | Chunk(bt >> BIG.BASEBITS)
/*
        let x0=a&BIG.HMASK;
        let x1=(a>>Chunk(BIG.HBITS))
        let y0=b&BIG.HMASK;
        let y1=(b>>Chunk(BIG.HBITS))
        var bot=x0*y0
        var top=x1*y1
        let mid=x0*y1+x1*y0
        let u0=mid&BIG.HMASK
        let u1=(mid>>Chunk(BIG.HBITS))
        bot=bot+(u0<<Chunk(BIG.HBITS))
	top+=u1
*/
        bot+=c; bot+=r
        let carry=bot>>Chunk(BIG.BASEBITS)
        bot &= BIG.BMASK
        top+=carry
        return (top,bot)
    }
    
#endif
    /* test for zero */
    func iszilch() -> Bool
    {
        for i in 0 ..< BIG.NLEN {if w[i] != 0 {return false}}
        return true
    }
/* set to zero */
    mutating func zero()
    {
        for i in 0 ..< BIG.NLEN {w[i] = 0}
    }
/* set to one */
    mutating func one()
    {
        w[0]=1
        for i in 1 ..< BIG.NLEN {w[i]=0}
    }
/* Test for equal to one */
    func isunity() -> Bool
    {
        for i in 1 ..< 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 ..< BIG.NLEN {w[i] = x.w[i]}
    }
    mutating func copy(_ x: DBIG)
    {
        for i in 0 ..< 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 ..< 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 ..< BIG.NLEN
        {
            w[i]^=(w[i]^g.w[i])&b;
        }
    }
/* normalise BIG - force all digits < 2^BIG.BASEBITS */
    @discardableResult mutating func norm() -> Chunk
    {
        var carry=Chunk(0);
        for i in 0 ..< BIG.NLEN-1
        {
            let d=w[i]+carry
            w[i]=d&BIG.BMASK
            carry=d>>Chunk(BIG.BASEBITS)
        }
        w[BIG.NLEN-1]+=carry
        return (w[BIG.NLEN-1]>>Chunk((8*BIG.MODBYTES)%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 ..< BIG.NLEN-1
        {
            w[i]=(w[i]>>kw)|((w[i+1]<<(Chunk(BIG.BASEBITS)-kw))&BIG.BMASK)
        }
        w[BIG.NLEN-1]>>=kw;
        return Int(r)
    }
/* general shift right */
    mutating func shr(_ k: UInt)
    {
        let n=k%BIG.BASEBITS
        let m=Int(k/BIG.BASEBITS)
        for i in 0 ..< BIG.NLEN-m-1
        {
            w[i]=(w[m+i]>>Chunk(n))|((w[m+i+1]<<Chunk(BIG.BASEBITS-n))&BIG.BMASK)
        }
        w[BIG.NLEN - m - 1]=w[BIG.NLEN-1]>>Chunk(n)
        for i in BIG.NLEN - m ..< BIG.NLEN {w[i]=0}
    }
/* Shift right by less than a word */
    @discardableResult mutating func fshl(_ k: Int) -> Int
    {
        let kw=Chunk(k)
        w[BIG.NLEN-1]=((w[BIG.NLEN-1]<<kw))|(w[BIG.NLEN-2]>>(Chunk(BIG.BASEBITS)-kw))
        for i in (1...BIG.NLEN-2).reversed()
        {
            w[i]=((w[i]<<kw)&BIG.BMASK)|(w[i-1]>>(Chunk(BIG.BASEBITS)-kw))
        }
        w[0]=(w[0]<<kw)&BIG.BMASK
        return Int(w[BIG.NLEN-1]>>Chunk((8*BIG.MODBYTES)%BIG.BASEBITS))
    }
/* general shift left */
    mutating func shl(_ k: UInt)
    {
        let n=k%BIG.BASEBITS
        let m=Int(k/BIG.BASEBITS)
        
        w[BIG.NLEN-1]=(w[BIG.NLEN-1-m]<<Chunk(n))
        if BIG.NLEN>=m+2 {w[BIG.NLEN-1]|=(w[BIG.NLEN-m-2]>>Chunk(BIG.BASEBITS-n))}
        for i in (m+1...BIG.NLEN-2).reversed()
        {
            w[i]=((w[i-m]<<Chunk(n))&BIG.BMASK)|(w[i-m-1]>>Chunk(BIG.BASEBITS-n))
        }
        w[m]=(w[0]<<Chunk(n))&BIG.BMASK
        for i in 0 ..< m {w[i]=0}
    }
/* return number of bits */
    func nbits() -> Int
    {
        var k=(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(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 ..< BIG.NLEN-1
        {
            let n=String(w[i],radix:16,uppercase:false)
            s+=n
            s+=","
            
        }
        let n=String(w[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(BIG.MODBYTES) {len=2*Int(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 ..< BIG.NLEN
        {
            s.w[i]=w[i]+x.w[i]
        }
        return s
    }
/* this+=x */
    mutating func add(_ x: BIG)
    {
        for i in 0 ..< BIG.NLEN
        {
            w[i]+=x.w[i]
        }
    }

/* this|=x */
    mutating func or(_ x: BIG)
    {
        for i in 0 ..< 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 ..< BIG.NLEN
        {
            d.w[i]=w[i]-x.w[i];
        }
        return d;
    }
/* this-=x */
    mutating func sub(_ x: BIG)
    {
        for i in 0 ..< BIG.NLEN
        {
            w[i]-=x.w[i]
        }
    }
/* reverse subtract this=x-this */
    mutating func rsub(_ x: BIG)
    {
        for i in 0 ..< 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 ..< 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(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(BIG.MODBYTES)
        {
            m.fshl(8)
            m.w[0]+=Chunk(b[i+n])&0xff    //(int)b[i+n]&0xff;
        }
        return m;
    }
    func toBytes(_ b: inout [UInt8])
    {
        tobytearray(&b,0)
    }
    static func fromBytes(_ b: [UInt8]) -> BIG
    {
        return frombytearray(b,0)
    }
/* set this[i]+=x*y+c, and return high part
    func muladd(_ x: Int32,_ y: Int32,_ c: Int32,_ i: Int) -> Int32
    {
        let prod:DChunk = DChunk(x)*DChunk(y)+DChunk(c)+DChunk(w[i])
        w[i]=Int32(prod&DChunk(BIG.BMASK))
        return Int32(prod>>DChunk(BIG.BASEBITS))
    } */

/* this*=x, where x is >NEXCESS */
    @discardableResult mutating func pmul(_ c: Int) -> Chunk
    {
        var carry=Chunk(0);
        //norm();
        for i in 0 ..< 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 ..< BIG.NLEN
        {
            let (top,bot)=BIG.muladd(w[j],Chunk(c),carry,m.w[j])
            carry=top; m.w[j]=bot
        }
        m.w[BIG.NLEN]=carry
        return m;
    }
/* divide by 3 */
    mutating func div3() -> Chunk
    {
        var carry=Chunk(0)
        norm();
        let base=Chunk(1<<BIG.BASEBITS);
        for i in (0...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 ..< BIG.NLEN
        {
            var carry=Chunk(0)
            for j in 0 ..< BIG.NLEN
            {
                if (i+j<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
                    //carry=c.muladd(a.w[i],b.w[j],carry,i+j)
                }
            }
        }
        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...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/BIG.BASEBITS)
        let bt=m%BIG.BASEBITS
        let msk=Chunk(1<<bt)-1;
        w[wd]&=msk;
        for i in wd+1 ..< 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/BIG.BASEBITS)]&(1<<Chunk(n%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<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(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[BIG.NLEN-1]>>Chunk(BIG.CHUNK-1))&1)))
/*
            if (BIG.comp(self,m)>=0)
            {
				sub(m)
				norm()
            } */
            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[BIG.NLEN-1]>>Chunk(BIG.CHUNK-1))&1))
		b.cmove(r,d)
		r.copy(self)
		r.add(e)
		r.norm()
		cmove(r,d)
/*
            if (BIG.comp(b,m)>=0)
            {
				add(e)
				norm()
				b.sub(m)
				b.norm()
            } */
            k -= 1;
        }
    }
    /* get 8*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*BIG.MODBYTES)
        {
            if (j==0) {r=rng.getByte()}
            else {r>>=1}
    
            let b=Chunk(r&1);
            m.shl(1); m.w[0]+=b;// m.inc(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; // m.inc(b);
            j += 1; j&=7;
        }
        let m=d.mod(q);
        return m;
    }
    
    /* return NAF value as +/- 1, 3 or 5. x and x3 should be normed.
    nbs is number of bits processed, and nzs is number of trailing 0s detected
    static func nafbits(_ x: BIG,_ x3:BIG ,i:Int) -> [Chunk]
    {
        var j:Int
        var n=[Chunk](repeating: 0,count: 3)
        var nb=x3.bit(UInt(i))-x.bit(UInt(i))
        n[1]=1;
        n[0]=0;
        if (nb==0) {n[0]=0; return n}
        if (i==0) {n[0]=Chunk(nb); return n}
        if (nb>0) {n[0]=1}
        else      {n[0]=(-1)}
    
        j=i-1
        while (true)
        {
            n[1] += 1
            n[0]*=2
            nb=x3.bit(UInt(j))-x.bit(UInt(j))
            if (nb>0) {n[0]+=1}
            if (nb<0) {n[0]-=1}
            if (n[0]>5 || n[0] < -5) {break}
            j-=1
            if j==0 {break}
        }
    
        if ((n[0]%2 != 0) && (j != 0))
        { // backtrack 
            if (nb>0) {n[0]=(n[0]-1)/2}
            if (nb<0) {n[0]=(n[0]+1)/2}
            n[1] -= 1;
        }
        while (n[0]%2==0)
        { // remove trailing zeros 
            n[0]/=2
            n[2] += 1
            n[1] -= 1
        }
        return n;
    } */
    
    /* 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(BIG.BMASK);
        let RB:DChunk=DChunk(BIG.BASEBITS)
   //     a.norm();
   //     b.norm();
        
        var d=[DChunk](repeating: 0,count: BIG.NLEN)
        var s:DChunk
        for i in 0 ..< 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 ..< 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 BIG.NLEN ..< 2*BIG.NLEN-1
        {
            s-=d[k-BIG.NLEN]; t=co+s;
  
            //for var i=BIG.NLEN-1;i>=1+k/2;i--
            var i=1+k/2
            while i<BIG.NLEN
            //for i in 1+k/2...BIG.NLEN-1
            {
                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*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(BIG.BMASK);
        let RB:DChunk=DChunk(BIG.BASEBITS)
   //     a.norm();

        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<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=BIG.NLEN-1+(BIG.NLEN%2)
        while j<BIG.DNLEN-3
        {
            t=DChunk(a.w[BIG.NLEN-1])*DChunk(a.w[j-BIG.NLEN+1]); for i in j-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[BIG.NLEN-1])*DChunk(a.w[j-BIG.NLEN+1]); for i in j-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[BIG.NLEN-2])*DChunk(a.w[BIG.NLEN-1])
        t+=t; t+=co;
        c.w[BIG.DNLEN-3]=Chunk(t&RM); co=t>>RB
    
        t=DChunk(a.w[BIG.NLEN-1])*DChunk(a.w[BIG.NLEN-1])+co
        c.w[BIG.DNLEN-2]=Chunk(t&RM); co=t>>RB
        c.w[BIG.DNLEN-1]=Chunk(co)


/*

        t=DChunk(a.w[0])*DChunk(a.w[0])
        c.w[0]=Chunk(t&RM); co=t>>RB
        t=DChunk(a.w[1])*DChunk(a.w[0]); t+=t; t+=co
        c.w[1]=Chunk(t&RM); co=t>>RB
        
        var j:Int
        let last=BIG.NLEN-(BIG.NLEN%2)
        j=2
        //for j=2;j<last;j+=2
        while (j<last)
        {
            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
            t=DChunk(a.w[j+1])*DChunk(a.w[0]); for i in 1 ..< (j+2)/2 {t+=DChunk(a.w[j+1-i])*DChunk(a.w[i])} ; t+=t; t+=co
            c.w[j+1]=Chunk(t&RM); co=t>>RB
            j+=2
        }
        j=last
        if (BIG.NLEN%2)==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
            t=DChunk(a.w[BIG.NLEN-1])*DChunk(a.w[j-BIG.NLEN+1]); for i in j-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
        }
        while (j<BIG.DNLEN-2)
        {
            t=DChunk(a.w[BIG.NLEN-1])*DChunk(a.w[j-BIG.NLEN+1]); for i in j-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
            t=DChunk(a.w[BIG.NLEN-1])*DChunk(a.w[j-BIG.NLEN+2]); for i in j-BIG.NLEN+3 ..< (j+2)/2 {t+=DChunk(a.w[j+1-i])*DChunk(a.w[i])} ; t+=t; t+=co
            c.w[j+1]=Chunk(t&RM); co=t>>RB
            j+=2
        }
        t=DChunk(a.w[BIG.NLEN-1])*DChunk(a.w[BIG.NLEN-1])+co
        c.w[BIG.DNLEN-2]=Chunk(t&RM); co=t>>RB
        c.w[BIG.DNLEN-1]=Chunk(co)
*/    
        return c;
    }
    static func monty(_ md:BIG,_ mc:Chunk,_ d: inout DBIG) -> BIG
    {
    //    let md=BIG(ROM.Modulus);
        let RM:DChunk=DChunk(BIG.BMASK)
        let RB:DChunk=DChunk(BIG.BASEBITS)
        
        
        var t:DChunk
        var s:DChunk
        var c:DChunk
        var dd=[DChunk](repeating: 0,count: BIG.NLEN)
        var v=[Chunk](repeating: 0,count: BIG.NLEN)
        var b=BIG(0)
        
        t=DChunk(d.w[0]); v[0]=(Chunk(t&RM)&*mc)&BIG.BMASK; t+=DChunk(v[0])*DChunk(md.w[0]); c=DChunk(d.w[1])+(t>>RB); s=0
        for k in 1 ..< BIG.NLEN
        {
            t=c+s+DChunk(v[0])*DChunk(md.w[k])
            //for i in 1+k/2...k-1
            //for var i=k-1;i>k/2;i--
            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)&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 BIG.NLEN ..< 2*BIG.NLEN-1
        {
            t=c+s;
            //for i in 1+k/2...BIG.NLEN-1
            //for var i=BIG.NLEN-1;i>=1+k/2;i--
            var i=1+k/2
            while i<BIG.NLEN
            {
                t+=DChunk(v[k-i]-v[i])*DChunk(md.w[i]-md.w[k-i])
                i+=1
            }
            b.w[k-BIG.NLEN]=Chunk(t&RM); c=DChunk(d.w[k+1])+(t>>RB); s-=dd[k-BIG.NLEN+1]
        }
        b.w[BIG.NLEN-1]=Chunk(c&RM)
     //   b.norm()
        return b;
    }
#endif
#if D64
    static func mul(_ a: BIG,_ b:BIG) -> DBIG
    {
        var c=DBIG()
        var carry:Chunk
        for i in 0 ..< BIG.NLEN {
            carry=0
            for j in 0..<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[BIG.NLEN+i]=carry
        }
        return c
    }
    static func sqr(_ a: BIG) -> DBIG
    {
        var c=DBIG()
        var carry:Chunk
        for i in 0 ..< BIG.NLEN {
            carry=0
            for j in i+1 ..< 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[BIG.NLEN+i]=carry
        }
        for i in 0 ..< 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()
    //    let md=BIG(ROM.Modulus);
        var carry:Chunk
        var m:Chunk
        for i in 0 ..< BIG.NLEN {
            if mc == -1 {
                m=(-d.w[i])&BIG.BMASK
            } else {
                if mc == 1 {
                    m=d.w[i]
                } else {
                    m=(mc&*d.w[i])&BIG.BMASK;
                }
            }
            carry=0
            for j in 0 ..< 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[BIG.NLEN+i]+=carry
        }
        for i in 0 ..< BIG.NLEN {
            b.w[i]=d.w[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=BIG.NLEN-1
        m.w[0]=(m.w[0]>>1)|((m.w[1]<<Chunk(BIG.BASEBITS-1))&BIG.BMASK)
        r.w[0]=a.w[0]-m.w[0]
        var carry=r.w[0]>>Chunk(BIG.BASEBITS)
        r.w[0] &= BIG.BMASK
        for i in 1 ..< n {
            m.w[i]=(m.w[i]>>1)|((m.w[i+1]<<Chunk(BIG.BASEBITS-1))&BIG.BMASK)
            r.w[i]=a.w[i]-m.w[i]+carry
            carry=r.w[i]>>Chunk(BIG.BASEBITS)
            r.w[i] &= BIG.BMASK
        }
	   m.w[n]>>=1
	   r.w[n]=a.w[n]-m.w[n]+carry
	   return Int((r.w[n]>>Chunk(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
    }
}