t_finite_fields_double_precision.nim
1 # Constantine 2 # Copyright (c) 2018-2019 Status Research & Development GmbH 3 # Copyright (c) 2020-Present Mamy André-Ratsimbazafy 4 # Licensed and distributed under either of 5 # * MIT license (license terms in the root directory or at http://opensource.org/licenses/MIT). 6 # * Apache v2 license (license terms in the root directory or at http://www.apache.org/licenses/LICENSE-2.0). 7 # at your option. This file may not be copied, modified, or distributed except according to those terms. 8 9 import 10 # Standard library 11 std/[unittest, times], 12 # Internal 13 ../../constantine/platforms/abstractions, 14 ../../constantine/math/arithmetic, 15 ../../constantine/math/io/[io_bigints, io_fields], 16 ../../constantine/math/config/[curves, type_bigint], 17 # Test utilities 18 ../../helpers/prng_unsafe 19 20 const Iters = 12 21 22 var rng: RngState 23 let seed = uint32(getTime().toUnix() and (1'i64 shl 32 - 1)) # unixTime mod 2^32 24 rng.seed(seed) 25 echo "\n------------------------------------------------------\n" 26 echo "test_finite_fields_double_precision xoshiro512** seed: ", seed 27 28 template addsubnegTest(rng_gen: untyped): untyped = 29 proc `addsubneg _ rng_gen`(C: static Curve) = 30 # Try to exercise all code paths for in-place/out-of-place add/sum/sub/diff/double/neg 31 # (1 - (-a) - b + (-a) - 2a) + (2a + 2b + (-b)) == 1 32 let aFp = rng_gen(rng, Fp[C]) 33 let bFp = rng_gen(rng, Fp[C]) 34 var accumFp {.noInit.}: Fp[C] 35 var OneFp {.noInit.}: Fp[C] 36 var accum {.noInit.}, One {.noInit.}, a{.noInit.}, na{.noInit.}, b{.noInit.}, nb{.noInit.}, a2 {.noInit.}, b2 {.noInit.}: FpDbl[C] 37 38 OneFp.setOne() 39 One.prod2x(OneFp, OneFp) 40 a.prod2x(aFp, OneFp) 41 b.prod2x(bFp, OneFp) 42 43 block: # sanity check 44 var t: Fp[C] 45 t.redc2x(One) 46 doAssert bool t.isOne() 47 48 a2.sum2xMod(a, a) 49 na.neg2xMod(a) 50 51 block: # sanity check 52 var t0, t1: Fp[C] 53 t0.redc2x(na) 54 t1.neg(aFp) 55 doAssert bool(t0 == t1), 56 "Beware, if the hex are the same, it means the outputs are the same (mod p),\n" & 57 "but one might not be completely reduced\n" & 58 " t0: " & t0.toHex() & "\n" & 59 " t1: " & t1.toHex() & "\n" 60 61 block: # sanity check 62 var t0, t1: Fp[C] 63 t0.redc2x(a2) 64 t1.double(aFp) 65 doAssert bool(t0 == t1), 66 "Beware, if the hex are the same, it means the outputs are the same (mod p),\n" & 67 "but one might not be completely reduced\n" & 68 " t0: " & t0.toHex() & "\n" & 69 " t1: " & t1.toHex() & "\n" 70 71 b2.sum2xMod(b, b) 72 nb.neg2xMod(b) 73 74 accum.diff2xMod(One, na) 75 accum.diff2xMod(accum, b) 76 accum.sum2xMod(accum, na) 77 accum.diff2xMod(accum, a2) 78 79 var t{.noInit.}: FpDbl[C] 80 t.sum2xMod(a2, b2) 81 t.sum2xMod(t, nb) 82 83 accum.sum2xMod(accum, t) 84 accumFp.redc2x(accum) 85 doAssert bool accumFp.isOne(), 86 "Beware, if the hex are the same, it means the outputs are the same (mod p),\n" & 87 "but one might not be completely reduced\n" & 88 " accumFp: " & accumFp.toHex() 89 90 template mulTest(rng_gen: untyped): untyped = 91 proc `mul _ rng_gen`(C: static Curve) = 92 let a = rng_gen(rng, Fp[C]) 93 let b = rng_gen(rng, Fp[C]) 94 95 var r_fp{.noInit.}, r_fpDbl{.noInit.}: Fp[C] 96 var tmpDbl{.noInit.}: FpDbl[C] 97 98 r_fp.prod(a, b) 99 tmpDbl.prod2x(a, b) 100 r_fpDbl.redc2x(tmpDbl) 101 102 doAssert bool(r_fp == r_fpDbl) 103 104 template sqrTest(rng_gen: untyped): untyped = 105 proc `sqr _ rng_gen`(C: static Curve) = 106 let a = rng_gen(rng, Fp[C]) 107 108 var mulDbl{.noInit.}, sqrDbl{.noInit.}: FpDbl[C] 109 110 mulDbl.prod2x(a, a) 111 sqrDbl.square2x(a) 112 113 doAssert bool(mulDbl == sqrDbl), 114 "\nOriginal: " & a.mres.limbs.toString() & 115 "\n Mul: " & mulDbl.limbs2x.toString() & 116 "\n Sqr: " & sqrDbl.limbs2x.toString() 117 118 addsubnegTest(random_unsafe) 119 addsubnegTest(randomHighHammingWeight) 120 addsubnegTest(random_long01Seq) 121 mulTest(random_unsafe) 122 mulTest(randomHighHammingWeight) 123 mulTest(random_long01Seq) 124 sqrTest(random_unsafe) 125 sqrTest(randomHighHammingWeight) 126 sqrTest(random_long01Seq) 127 128 suite "Field Addition/Substraction/Negation via double-precision field elements" & " [" & $WordBitWidth & "-bit words]": 129 test "With P-224 field modulus": 130 for _ in 0 ..< Iters: 131 addsubneg_random_unsafe(P224) 132 for _ in 0 ..< Iters: 133 addsubneg_randomHighHammingWeight(P224) 134 for _ in 0 ..< Iters: 135 addsubneg_random_long01Seq(P224) 136 137 test "With P-256 field modulus": 138 for _ in 0 ..< Iters: 139 addsubneg_random_unsafe(P256) 140 for _ in 0 ..< Iters: 141 addsubneg_randomHighHammingWeight(P256) 142 for _ in 0 ..< Iters: 143 addsubneg_random_long01Seq(P256) 144 145 test "With BN254_Snarks field modulus": 146 for _ in 0 ..< Iters: 147 addsubneg_random_unsafe(BN254_Snarks) 148 for _ in 0 ..< Iters: 149 addsubneg_randomHighHammingWeight(BN254_Snarks) 150 for _ in 0 ..< Iters: 151 addsubneg_random_long01Seq(BN254_Snarks) 152 153 test "With BLS12_381 field modulus": 154 for _ in 0 ..< Iters: 155 addsubneg_random_unsafe(BLS12_381) 156 for _ in 0 ..< Iters: 157 addsubneg_randomHighHammingWeight(BLS12_381) 158 for _ in 0 ..< Iters: 159 addsubneg_random_long01Seq(BLS12_381) 160 161 test "With Edwards25519 field modulus": 162 for _ in 0 ..< Iters: 163 addsubneg_random_unsafe(Edwards25519) 164 for _ in 0 ..< Iters: 165 addsubneg_randomHighHammingWeight(Edwards25519) 166 for _ in 0 ..< Iters: 167 addsubneg_random_long01Seq(Edwards25519) 168 169 test "With Bandersnatch field modulus": 170 for _ in 0 ..< Iters: 171 addsubneg_random_unsafe(Bandersnatch) 172 for _ in 0 ..< Iters: 173 addsubneg_randomHighHammingWeight(Bandersnatch) 174 for _ in 0 ..< Iters: 175 addsubneg_random_long01Seq(Bandersnatch) 176 177 test "With Pallas field modulus": 178 for _ in 0 ..< Iters: 179 addsubneg_random_unsafe(Pallas) 180 for _ in 0 ..< Iters: 181 addsubneg_randomHighHammingWeight(Pallas) 182 for _ in 0 ..< Iters: 183 addsubneg_random_long01Seq(Pallas) 184 185 test "With Vesta field modulus": 186 for _ in 0 ..< Iters: 187 addsubneg_random_unsafe(Vesta) 188 for _ in 0 ..< Iters: 189 addsubneg_randomHighHammingWeight(Vesta) 190 for _ in 0 ..< Iters: 191 addsubneg_random_long01Seq(Vesta) 192 193 test "Negate 0 returns 0 (unique Montgomery repr)": 194 var a: FpDbl[BN254_Snarks] 195 var r {.noInit.}: FpDbl[BN254_Snarks] 196 r.neg2xMod(a) 197 198 check: bool r.isZero() 199 200 suite "Field Multiplication via double-precision field elements is consistent with single-width." & " [" & $WordBitWidth & "-bit words]": 201 test "With P-224 field modulus": 202 for _ in 0 ..< Iters: 203 mul_random_unsafe(P224) 204 for _ in 0 ..< Iters: 205 mul_randomHighHammingWeight(P224) 206 for _ in 0 ..< Iters: 207 mul_random_long01Seq(P224) 208 209 test "With P-256 field modulus": 210 for _ in 0 ..< Iters: 211 mul_random_unsafe(P256) 212 for _ in 0 ..< Iters: 213 mul_randomHighHammingWeight(P256) 214 for _ in 0 ..< Iters: 215 mul_random_long01Seq(P256) 216 217 test "With BN254_Snarks field modulus": 218 for _ in 0 ..< Iters: 219 mul_random_unsafe(BN254_Snarks) 220 for _ in 0 ..< Iters: 221 mul_randomHighHammingWeight(BN254_Snarks) 222 for _ in 0 ..< Iters: 223 mul_random_long01Seq(BN254_Snarks) 224 225 test "With BLS12_381 field modulus": 226 for _ in 0 ..< Iters: 227 mul_random_unsafe(BLS12_381) 228 for _ in 0 ..< Iters: 229 mul_randomHighHammingWeight(BLS12_381) 230 for _ in 0 ..< Iters: 231 mul_random_long01Seq(BLS12_381) 232 233 test "With Edwards25519 field modulus": 234 for _ in 0 ..< Iters: 235 mul_random_unsafe(Edwards25519) 236 for _ in 0 ..< Iters: 237 mul_randomHighHammingWeight(Edwards25519) 238 for _ in 0 ..< Iters: 239 mul_random_long01Seq(Edwards25519) 240 241 test "With Bandersnatch field modulus": 242 for _ in 0 ..< Iters: 243 mul_random_unsafe(Bandersnatch) 244 for _ in 0 ..< Iters: 245 mul_randomHighHammingWeight(Bandersnatch) 246 for _ in 0 ..< Iters: 247 mul_random_long01Seq(Bandersnatch) 248 249 test "With Pallas field modulus": 250 for _ in 0 ..< Iters: 251 mul_random_unsafe(Pallas) 252 for _ in 0 ..< Iters: 253 mul_randomHighHammingWeight(Pallas) 254 for _ in 0 ..< Iters: 255 mul_random_long01Seq(Pallas) 256 257 test "With Vesta field modulus": 258 for _ in 0 ..< Iters: 259 mul_random_unsafe(Vesta) 260 for _ in 0 ..< Iters: 261 mul_randomHighHammingWeight(Vesta) 262 for _ in 0 ..< Iters: 263 mul_random_long01Seq(Vesta) 264 265 suite "Field Squaring via double-precision field elements is consistent with single-width." & " [" & $WordBitWidth & "-bit words]": 266 test "With P-224 field modulus": 267 for _ in 0 ..< Iters: 268 sqr_random_unsafe(P224) 269 for _ in 0 ..< Iters: 270 sqr_randomHighHammingWeight(P224) 271 for _ in 0 ..< Iters: 272 sqr_random_long01Seq(P224) 273 274 test "With P-256 field modulus": 275 for _ in 0 ..< Iters: 276 sqr_random_unsafe(P256) 277 for _ in 0 ..< Iters: 278 sqr_randomHighHammingWeight(P256) 279 for _ in 0 ..< Iters: 280 sqr_random_long01Seq(P256) 281 282 test "With BN254_Snarks field modulus": 283 for _ in 0 ..< Iters: 284 sqr_random_unsafe(BN254_Snarks) 285 for _ in 0 ..< Iters: 286 sqr_randomHighHammingWeight(BN254_Snarks) 287 for _ in 0 ..< Iters: 288 sqr_random_long01Seq(BN254_Snarks) 289 290 test "With BLS12_381 field modulus": 291 for _ in 0 ..< Iters: 292 sqr_random_unsafe(BLS12_381) 293 for _ in 0 ..< Iters: 294 sqr_randomHighHammingWeight(BLS12_381) 295 for _ in 0 ..< Iters: 296 sqr_random_long01Seq(BLS12_381) 297 298 test "With Edwards25519 field modulus": 299 for _ in 0 ..< Iters: 300 sqr_random_unsafe(Edwards25519) 301 for _ in 0 ..< Iters: 302 sqr_randomHighHammingWeight(Edwards25519) 303 for _ in 0 ..< Iters: 304 sqr_random_long01Seq(Edwards25519) 305 306 test "With Bandersnatch field modulus": 307 for _ in 0 ..< Iters: 308 sqr_random_unsafe(Bandersnatch) 309 for _ in 0 ..< Iters: 310 sqr_randomHighHammingWeight(Bandersnatch) 311 for _ in 0 ..< Iters: 312 sqr_random_long01Seq(Bandersnatch) 313 314 test "With Pallas field modulus": 315 for _ in 0 ..< Iters: 316 sqr_random_unsafe(Pallas) 317 for _ in 0 ..< Iters: 318 sqr_randomHighHammingWeight(Pallas) 319 for _ in 0 ..< Iters: 320 sqr_random_long01Seq(Pallas) 321 322 test "With Vesta field modulus": 323 for _ in 0 ..< Iters: 324 sqr_random_unsafe(Vesta) 325 for _ in 0 ..< Iters: 326 sqr_randomHighHammingWeight(Vesta) 327 for _ in 0 ..< Iters: 328 sqr_random_long01Seq(Vesta)