1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139
// Copyright (C) 2019-2021 Aleo Systems Inc. // This file is part of the snarkVM library. // The snarkVM library is free software: you can redistribute it and/or modify // it under the terms of the GNU General Public License as published by // the Free Software Foundation, either version 3 of the License, or // (at your option) any later version. // The snarkVM library is distributed in the hope that it will be useful, // but WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the // GNU General Public License for more details. // You should have received a copy of the GNU General Public License // along with the snarkVM library. If not, see <https://www.gnu.org/licenses/>. use snarkvm_fields::{FftParameters, FieldParameters, Fp256, Fp256Parameters}; use snarkvm_utilities::biginteger::BigInteger256 as BigInteger; /// BLS12-377 scalar field. /// /// Roots of unity computed from modulus and R using this sage code: /// /// ```ignore /// q = 8444461749428370424248824938781546531375899335154063827935233455917409239041 /// R = 6014086494747379908336260804527802945383293308637734276299549080986809532403 # Montgomery R /// s = 47 /// o = q - 1 /// F = GF(q) /// g = F.multiplicative_generator() /// assert g.multiplicative_order() == o /// g2 = g ** (o/2**s) /// assert g2.multiplicative_order() == 2**s /// def into_chunks(val, width, n): /// return [int(int(val) // (2 ** (width * i)) % 2 ** width) for i in range(n)] /// print("Gen: ", g * R % q) /// print("Gen: ", into_chunks(g * R % q, 64, 4)) /// print("2-adic gen: ", into_chunks(g2 * R % q, 64, 4)) /// ``` pub type Fr = Fp256<FrParameters>; pub struct FrParameters; impl Fp256Parameters for FrParameters {} impl FftParameters for FrParameters { type BigInteger = BigInteger; #[rustfmt::skip] const TWO_ADICITY: u32 = 47; /// TODO (howardwu): CRITICAL - Fix this after a migration plan has been determined. /// - 0x3c3d3ca739381fb2, /// - 0x9a14cda3ec99772b, /// - 0xd7aacc7c59724826, /// - 0xd1ba211c5cc349c, /// + 12646347781564978760u64, /// + 6783048705277173164u64, /// + 268534165941069093u64, /// + 1121515446318641358u64, #[rustfmt::skip] const TWO_ADIC_ROOT_OF_UNITY: BigInteger = BigInteger([ 0x3c3d3ca739381fb2, 0x9a14cda3ec99772b, 0xd7aacc7c59724826, 0xd1ba211c5cc349c, ]); } impl FieldParameters for FrParameters { #[rustfmt::skip] const CAPACITY: u32 = Self::MODULUS_BITS - 1; /// GENERATOR = 22 /// Encoded in Montgomery form, so the value is /// (22 * R) % q = 5642976643016801619665363617888466827793962762719196659561577942948671127251 #[rustfmt::skip] const GENERATOR: BigInteger = BigInteger([ 2984901390528151251u64, 10561528701063790279u64, 5476750214495080041u64, 898978044469942640u64, ]); #[rustfmt::skip] const INV: u64 = 725501752471715839u64; /// MODULUS = 8444461749428370424248824938781546531375899335154063827935233455917409239041 #[rustfmt::skip] const MODULUS: BigInteger = BigInteger([ 725501752471715841u64, 6461107452199829505u64, 6968279316240510977u64, 1345280370688173398u64, ]); #[rustfmt::skip] const MODULUS_BITS: u32 = 253; /// (r - 1)/2 = /// 4222230874714185212124412469390773265687949667577031913967616727958704619520 #[rustfmt::skip] const MODULUS_MINUS_ONE_DIV_TWO: BigInteger = BigInteger([ 0x8508c00000000000, 0xacd53b7f68000000, 0x305a268f2e1bd800, 0x955b2af4d1652ab, ]); #[rustfmt::skip] const R: BigInteger = BigInteger([ 9015221291577245683u64, 8239323489949974514u64, 1646089257421115374u64, 958099254763297437u64, ]); #[rustfmt::skip] const R2: BigInteger = BigInteger([ 2726216793283724667u64, 14712177743343147295u64, 12091039717619697043u64, 81024008013859129u64, ]); #[rustfmt::skip] const REPR_SHAVE_BITS: u32 = 3; // T and T_MINUS_ONE_DIV_TWO, where r - 1 = 2^s * t /// t = (r - 1) / 2^s = /// 60001509534603559531609739528203892656505753216962260608619555 #[rustfmt::skip] const T: BigInteger = BigInteger([ 0xedfda00000021423, 0x9a3cb86f6002b354, 0xcabd34594aacc168, 0x2556, ]); /// (t - 1) / 2 = /// 30000754767301779765804869764101946328252876608481130304309777 #[rustfmt::skip] const T_MINUS_ONE_DIV_TWO: BigInteger = BigInteger([ 0x76fed00000010a11, 0x4d1e5c37b00159aa, 0x655e9a2ca55660b4, 0x12ab, ]); }