yaole
137 lines
7.5 KiB
Go
137 lines
7.5 KiB
Go
package bn256
|
|
|
|
import (
|
|
"math/big"
|
|
)
|
|
|
|
const numBytes = 256 / 8
|
|
|
|
func bigFromBase10(s string) *big.Int {
|
|
n, _ := new(big.Int).SetString(s, 10)
|
|
return n
|
|
}
|
|
|
|
func bigFromBase16(s string) *big.Int {
|
|
n, _ := new(big.Int).SetString(s, 16)
|
|
return n
|
|
}
|
|
|
|
// u is the BN parameter that determines the prime: 1868033³.
|
|
var u = bigFromBase16("600000000058F98A")
|
|
|
|
// P is a prime over which we form a basic field: 36u⁴+36u³+24u²+6u+1.
|
|
var P = bigFromBase16("B640000002A3A6F1D603AB4FF58EC74521F2934B1A7AEEDBE56F9B27E351457D")
|
|
|
|
// N is the number of elements in both G₁ and G₂: 36u⁴+36u³+18u²+6u+1.
|
|
var N = bigFromBase16("B640000002A3A6F1D603AB4FF58EC74449F2934B18EA8BEEE56EE19CD69ECF25")
|
|
|
|
// nMinusOne equals N-1.
|
|
// Note that N-1 = (2**5) * 3 * 5743 * 280941149 * 130979359433191 * 491513138693455212421542731357 * 6518589491078791937
|
|
var nMinusOne = bigFromBase16("B640000002A3A6F1D603AB4FF58EC74449F2934B18EA8BEEE56EE19CD69ECF24")
|
|
|
|
// pPlus1Over4 little-endian representation of (p-1) / 4
|
|
// var pPlus1Over4 = [4]uint64{0xf95be6c9f8d4515f, 0x487ca4d2c69ebbb6, 0x7580ead3fd63b1d1, 0x2d90000000a8e9bc}
|
|
|
|
var pMinus1Over2 = [4]uint64{0xf2b7cd93f1a8a2be, 0x90f949a58d3d776d, 0xeb01d5a7fac763a2, 0x5b2000000151d378}
|
|
var pMinus1 = [4]uint64{0xe56f9b27e351457c, 0x21f2934b1a7aeedb, 0xd603ab4ff58ec745, 0xb640000002a3a6f1}
|
|
var pMinus2 = [4]uint64{0xe56f9b27e351457b, 0x21f2934b1a7aeedb, 0xd603ab4ff58ec745, 0xb640000002a3a6f1}
|
|
var pPlus3Over8 = [4]uint64{0x7cadf364fc6a28b0, 0xa43e5269634f5ddb, 0x3ac07569feb1d8e8, 0x16c80000005474de}
|
|
var pMinus5Over8 = [4]uint64{0x7cadf364fc6a28af, 0xa43e5269634f5ddb, 0x3ac07569feb1d8e8, 0x16c80000005474de}
|
|
|
|
var sqrtRootOfMinus1ModP = &gfP{0xabbaac18a46a2054, 0x46ee57561222c759, 0x1dae609fa0e23561, 0x1df7113dae0adc3c}
|
|
|
|
// p2 is P
|
|
var p2 = [4]uint64{0xe56f9b27e351457d, 0x21f2934b1a7aeedb, 0xd603ab4ff58ec745, 0xb640000002a3a6f1} // nolint
|
|
|
|
// // np = -P^{-1} mod 2^256 is the negative inverse of P, mod 2^256.
|
|
var np = [4]uint64{0x892bc42c2f2ee42b, 0x181ae39613c8dbaf, 0x966a4b291522b137, 0xafd2bac5558a13b3} // nolint
|
|
|
|
// r is the Montgemory reprents of 1, r = R % p where R = 2^256
|
|
var r = [4]uint64{0x1a9064d81caeba83, 0xde0d6cb4e5851124, 0x29fc54b00a7138ba, 0x49bffffffd5c590e}
|
|
|
|
// gfPOne is the same as r
|
|
var gfPOne = gfP{0x1a9064d81caeba83, 0xde0d6cb4e5851124, 0x29fc54b00a7138ba, 0x49bffffffd5c590e}
|
|
|
|
// gfPZero is the 0
|
|
var gfPZero = gfP{0}
|
|
|
|
// nr is the Montgemory reprents of -1, r = -R % p where R = 2^256
|
|
var nr = [4]uint64{0xcadf364fc6a28afa, 0x43e5269634f5ddb7, 0xac07569feb1d8e8a, 0x6c80000005474de3}
|
|
|
|
// r2 is the Montgemory reprents of R, i.e., r2 = R^2%p.
|
|
var r2 = &gfP{0x27dea312b417e2d2, 0x88f8105fae1a5d3f, 0xe479b522d6706e7b, 0x2ea795a656f62fbd}
|
|
|
|
// r3 is the Montgemory reprents of R^2, i.e., r3 = R^3%p.
|
|
var r3 = &gfP{0x130257769df5827e, 0x36920fc0837ec76e, 0xcbec24519c22a142, 0x219be84a7c687090}
|
|
|
|
var rN1 = &gfP{0x0a1c7970e5df544d, 0xe74504e9a96b56cc, 0xcda02d92d4d62924, 0x7d2bc576fdf597d1} // nolint
|
|
|
|
var p = &gfP{0xe56f9b27e351457d, 0x21f2934b1a7aeedb, 0xd603ab4ff58ec745, 0xb640000002a3a6f1} // nolint
|
|
|
|
// montgomery encode of u^{p-1}, xiToPMinus1 = u^{p-1} * R % p = 2^{(p-1)/2} * R % p.
|
|
// used for Frob. map: frob(xu+y) = x*xiToPMinus1 * u + y
|
|
var xiToPMinus1 = &gfP{0xcadf364fc6a28afa, 0x43e5269634f5ddb7, 0xac07569feb1d8e8a, 0x6c80000005474de3} // nolint
|
|
|
|
var xiToPMinus1Over2 = &gfP{0xf5b21fd3da24d011, 0x9f9d411806dc5177, 0xf55acc93ee0baf15, 0x6c648de5dc0a3f2c} // nolint
|
|
|
|
var xiTo2PSquaredMinus2Over3 = &gfP{0x2f4981aa150a0eb3, 0x19c92815c28ded55, 0x39934d9cf7fd761b, 0x99cac18b7ca1dd5f}
|
|
var xiToPSquaredMinus1Over3 = &gfP{0x81054fcd94e9c1c4, 0x4c0e91cb8ce2df3e, 0x4877b452e8aedfb4, 0x88f53e748b491776}
|
|
var xiToPSquaredMinus1Over6 = &gfP{0xb626197dce4736ca, 0x08296b3557ed0186, 0x9c705db2fd91512a, 0x1c753e748601c992}
|
|
var xiTo2PMinus2Over3 = &gfP{0x81054fcd94e9c1c4, 0x4c0e91cb8ce2df3e, 0x4877b452e8aedfb4, 0x88f53e748b491776}
|
|
var xiToPMinus1Over3 = &gfP{0xb626197dce4736ca, 0x08296b3557ed0186, 0x9c705db2fd91512a, 0x1c753e748601c992}
|
|
var xiToPMinus1Over6 = &gfP{0x1a98dfbd4575299f, 0x9ec8547b245c54fd, 0xf51f5eac13df846c, 0x9ef74015d5a16393}
|
|
var xiTo2Minus2POver3 = &gfP{0x2f4981aa150a0eb3, 0x19c92815c28ded55, 0x39934d9cf7fd761b, 0x99cac18b7ca1dd5f}
|
|
var xiTo1MinusPOver3 = &gfP{0x646a4b5a4e6783b9, 0xd5e4017f8d980f9d, 0x8d8bf6fd0cdfe790, 0x2d4ac18b775a8f7b}
|
|
var xiTo1MinusPOver2 = &gfP{0xabbaac18a46a2054, 0x46ee57561222c759, 0x1dae609fa0e23561, 0x1df7113dae0adc3c}
|
|
|
|
//// xiToPMinus1Over6 is ξ^((P-1)/6) where ξ = i+3.
|
|
//var xiToPMinus1Over6 = &gfP2{gfP{0x25af52988477cdb7, 0x3d81a455ddced86a, 0x227d012e872c2431, 0x179198d3ea65d05}, gfP{0x7407634dd9cca958, 0x36d5bd6c7afb8f26, 0xf4b1c32cebd880fa, 0x6aa7869306f455f}}
|
|
//
|
|
//// xiToPMinus1Over3 is ξ^((P-1)/3) where ξ = i+3.
|
|
//var xiToPMinus1Over3 = &gfP2{gfP{0x4f59e37c01832e57, 0xae6be39ac2bbbfe4, 0xe04ea1bb697512f8, 0x3097caa8fc40e10e}, gfP{0xf8606916d3816f2c, 0x1e5c0d7926de927e, 0xbc45f3946d81185e, 0x80752a25aa738091}}
|
|
//
|
|
//// xiToPMinus1Over2 is ξ^((P-1)/2) where ξ = i+3.
|
|
//var xiToPMinus1Over2 = &gfP2{gfP{0x19da71333653ee20, 0x7eaaf34fc6ed6019, 0xc4ba3a29a60cdd1d, 0x75281311bcc9df79}, gfP{0x18dbee03fb7708fa, 0x1e7601a602c843c7, 0x5dde0688cdb231cb, 0x86db5cf2c605a524}}
|
|
//
|
|
//// xiToPSquaredMinus1Over3 is ξ^((P²-1)/3) where ξ = i+3.
|
|
//var xiToPSquaredMinus1Over3 = &gfP{0x12d3cef5e1ada57d, 0xe2eca1463753babb, 0xca41e40ddccf750, 0x551337060397e04c}
|
|
//
|
|
//// xiTo2PSquaredMinus2Over3 is ξ^((2p²-2)/3) where ξ = i+3 (a cubic root of unity, mod P).
|
|
//var xiTo2PSquaredMinus2Over3 = &gfP{0x3642364f386c1db8, 0xe825f92d2acd661f, 0xf2aba7e846c19d14, 0x5a0bcea3dc52b7a0}
|
|
//
|
|
//// xiToPSquaredMinus1Over6 is ξ^((1p²-1)/6) where ξ = i+3 (a cubic root of -1, mod P).
|
|
//var xiToPSquaredMinus1Over6 = &gfP{0xe21a761d259c78af, 0x6358fa3f5e84f7e, 0xb7c444d01ac33f0d, 0x35a9333f6e50d058}
|
|
//
|
|
//// xiTo2PMinus2Over3 is ξ^((2p-2)/3) where ξ = i+3.
|
|
//var xiTo2PMinus2Over3 = &gfP2{gfP{0x51678e7469b3c52a, 0x4fb98f8b13319fc9, 0x29b2254db3f1df75, 0x1c044935a3d22fb2}, gfP{0x4d2ea218872f3d2c, 0x2fcb27fc4abe7b69, 0xd31d972f0e88ced9, 0x53adc04a00a73b15}}
|
|
//
|
|
//// p2 is P, represented as little-endian 64-bit words.
|
|
//var p2 = [4]uint64{0x185cac6c5e089667, 0xee5b88d120b5b59e, 0xaa6fecb86184dc21, 0x8fb501e34aa387f9}
|
|
//
|
|
//// np is the negative inverse of P, mod 2^256.
|
|
//var np = [4]uint64{0x2387f9007f17daa9, 0x734b3343ab8513c8, 0x2524282f48054c12, 0x38997ae661c3ef3c}
|
|
//
|
|
//// rN1 is R^-1 where R = 2^256 mod P.
|
|
//var rN1 = &gfP{0xcbb781e36236117d, 0xcc65f3bcec8c91b, 0x2eab68888ea1f515, 0x1fc5c0956f92f825}
|
|
//
|
|
//// r2 is R^2 where R = 2^256 mod P.
|
|
//var r2 = &gfP{0x9c21c3ff7e444f56, 0x409ed151b2efb0c2, 0xc6dc37b80fb1651, 0x7c36e0e62c2380b7}
|
|
//
|
|
//// r3 is R^3 where R = 2^256 mod P.
|
|
//var r3 = &gfP{0x2af2dfb9324a5bb8, 0x388f899054f538a4, 0xdf2ff66396b107a7, 0x24ebbbb3a2529292}
|
|
//
|
|
//// pPlus1Over4 is (P+1)/4.
|
|
//var pPlus1Over4 = [4]uint64{0x86172b1b1782259a, 0x7b96e234482d6d67, 0x6a9bfb2e18613708, 0x23ed4078d2a8e1fe}
|
|
//
|
|
//// pMinus2 is P-2.
|
|
//var pMinus2 = [4]uint64{0x185cac6c5e089665, 0xee5b88d120b5b59e, 0xaa6fecb86184dc21, 0x8fb501e34aa387f9}
|
|
//
|
|
//// pMinus1Over2 is (P-1)/2.
|
|
//var pMinus1Over2 = [4]uint64{0x0c2e56362f044b33, 0xf72dc468905adacf, 0xd537f65c30c26e10, 0x47da80f1a551c3fc}
|
|
|
|
// s is the Montgomery encoding of the square root of -3. Then, s = sqrt(-3) * 2^256 mod P.
|
|
var s = &gfP{0x236e675956be783b, 0x053957e6f379ab64, 0xe60789a768f4a5c4, 0x04f8979dd8bad754} // nolint
|
|
|
|
// sMinus1Over2 is the Montgomery encoding of (s-1)/2. Then, sMinus1Over2 = ( (s-1) / 2) * 2^256 mod P.
|
|
var sMinus1Over2 = &gfP{0x3642364f386c1db8, 0xe825f92d2acd661f, 0xf2aba7e846c19d14, 0x5a0bcea3dc52b7a0} // nolint
|