snarkvm_curves/bls12_377/
fr.rs

1// Copyright (c) 2019-2025 Provable Inc.
2// This file is part of the snarkVM library.
3
4// Licensed under the Apache License, Version 2.0 (the "License");
5// you may not use this file except in compliance with the License.
6// You may obtain a copy of the License at:
7
8// http://www.apache.org/licenses/LICENSE-2.0
9
10// Unless required by applicable law or agreed to in writing, software
11// distributed under the License is distributed on an "AS IS" BASIS,
12// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13// See the License for the specific language governing permissions and
14// limitations under the License.
15
16use snarkvm_fields::{
17    FftParameters,
18    FieldParameters,
19    Fp256,
20    Fp256Parameters,
21    PoseidonDefaultParameters,
22    PoseidonDefaultParametersEntry,
23};
24use snarkvm_utilities::biginteger::BigInteger256 as BigInteger;
25
26/// BLS12-377 scalar field.
27///
28/// Roots of unity computed from modulus and R using this sage code:
29///
30/// ```r,ignore
31/// q = 8444461749428370424248824938781546531375899335154063827935233455917409239041
32/// R = 6014086494747379908336260804527802945383293308637734276299549080986809532403 # Montgomery R
33/// s = 47
34/// o = q - 1
35/// F = GF(q)
36/// g = F.multiplicative_generator()
37/// assert g.multiplicative_order() == o
38/// g2 = g ** (o/2**s)
39/// assert g2.multiplicative_order() == 2**s
40/// def into_chunks(val, width, n):
41///     return [int(int(val) // (2 ** (width * i)) % 2 ** width) for i in range(n)]
42/// print("Gen (g % q): ", g % q)
43/// print("Gen (g * R % q): ", g * R % q)
44/// print("Gen into_chunks(g * R % q): ", into_chunks(g * R % q, 64, 4))
45/// print("2-adic gen (g2 % q): ", g2 % q)
46/// print("2-adic gen (g2 * R % q): ", g2 * R % q)
47/// print("2-adic gen into_chunks(g2 * R % q): ", into_chunks(g2 * R % q, 64, 4))
48/// ```
49pub type Fr = Fp256<FrParameters>;
50
51#[derive(Copy, Clone, Debug, Default, PartialEq, Eq, Hash)]
52pub struct FrParameters;
53
54impl Fp256Parameters for FrParameters {}
55
56impl FftParameters for FrParameters {
57    type BigInteger = BigInteger;
58
59    #[rustfmt::skip]
60    const POWERS_OF_ROOTS_OF_UNITY: &'static [BigInteger] = &[
61        BigInteger([12646347781564978760, 6783048705277173164, 268534165941069093, 1121515446318641358]),
62        BigInteger([9908812190343590727, 989981212292874635, 13217848517394370016, 313220887743686251]),
63        BigInteger([4570942453055933478, 14327950181157151272, 8177734713484223276, 732395113570565582]),
64        BigInteger([7547026561639937065, 11733968610145256351, 8343216976141027051, 576989125389526455]),
65        BigInteger([15503117548499178639, 2308620569553928151, 16285062430639685160, 103769458534362861]),
66        BigInteger([8608407781632583430, 6271302370352858992, 1070338101025660973, 538942973387907962]),
67        BigInteger([6401736382236295208, 1153288719752352283, 14823640363840104239, 499246014633910619]),
68        BigInteger([17833850933386010261, 6090852137313170745, 12528041030915574153, 857737301371729770]),
69        BigInteger([1982048757083514280, 12158391317477180280, 13684570609270614441, 840786117129730731]),
70        BigInteger([18189047035874409266, 10063848728508956944, 18125989563719264563, 109154778261203350]),
71        BigInteger([4145860318443588715, 480045415555849201, 15185689511254420012, 997424544238423752]),
72        BigInteger([12380934610292147810, 14921791250714101079, 7953234348116523713, 740566716969780590]),
73        BigInteger([17523206016699816339, 8210268852326501515, 12102826939441359278, 69320453637394156]),
74        BigInteger([13184634841845083965, 5035641472528052881, 10848835132746879957, 1093292728521196096]),
75        BigInteger([3644591431389930536, 17535182174514028817, 2333780137994975086, 1211430046545197955]),
76        BigInteger([15764618857955124109, 17001304349044012093, 11249158843350648159, 1304234597518548509]),
77        BigInteger([17023740166556598291, 17327346947230052231, 15227607426000437488, 524356170404741496]),
78        BigInteger([15508095723619167236, 8916154698977858924, 4872918458681303657, 507246242966933127]),
79        BigInteger([13933261170268378635, 6975150440507062408, 285981162592700355, 909990229706841196]),
80        BigInteger([1796369225555089555, 18439169056424861976, 8554690303853538396, 739593369575156928]),
81        BigInteger([8849035624997270559, 11082174508102696985, 5797273297011026936, 458094565250654809]),
82        BigInteger([5944936778479914843, 369725202543584470, 22913969483319861, 1123237285519395196]),
83        BigInteger([8228193452833987056, 3247446711273005067, 7285244012699814841, 165660218100066147]),
84        BigInteger([16110965290454180518, 5418683100417587062, 11303731202360030209, 290121373407754357]),
85        BigInteger([10742665076645341070, 7056370150642984550, 12615465793934837989, 548498362185685512]),
86        BigInteger([8097456064175987351, 10585807130451162109, 5877015307964227995, 477368390704686837]),
87        BigInteger([15676770081073062471, 12262153699415403306, 7528677848461606057, 649917933945894399]),
88        BigInteger([18271947154240526633, 11103933895114620578, 16558660923152452318, 925331653431062360]),
89        BigInteger([3907589926240897769, 11045697709584246531, 90835143142482923, 870886311473863909]),
90        BigInteger([3528144693560331180, 11121597045360901952, 11405196888439666838, 670327805282996966]),
91        BigInteger([13456528212939925364, 9040660049171970165, 4374817133042500768, 422841521572866881]),
92        BigInteger([17220360707710309003, 7704697058569325505, 14703012148831508770, 113932329837224644]),
93        BigInteger([15456395681208503803, 6416534260312397167, 4409371950760456950, 855302230113322418]),
94        BigInteger([14648805411005782346, 659899539555743592, 13712138229698623536, 688628542983365223]),
95        BigInteger([17553691999655354057, 12414962864428128502, 12778610342023380950, 309906985245362430]),
96        BigInteger([13671771363231792901, 13550649581906397391, 14960300922341772840, 197239424530289859]),
97        BigInteger([14840183457516239942, 7651729362259515675, 11442121706837547178, 409184120412760908]),
98        BigInteger([5849560869621087513, 6649867980513935874, 16080766030443795594, 905356649678185654]),
99        BigInteger([13302147401216114106, 3611900969696901525, 3470557722594359823, 950175460673052306]),
100        BigInteger([16339580035428004219, 4845663562592066382, 6914211203719332907, 510216861370749871]),
101        BigInteger([2145222547635311650, 10230679325758658394, 7207487648880633871, 209805430256584658]),
102        BigInteger([9208812316068886018, 11169310505015993932, 8317257015293247865, 1090372203370214591]),
103        BigInteger([18408280738886485821, 14547869021980959191, 6047025381655759581, 725535874718029226]),
104        BigInteger([1670730338129557402, 7866724895305809984, 10026936948289003902, 781269171506367679]),
105        BigInteger([4882877962169421051, 8060560647985508350, 4729166814476724001, 1147730753089737444]),
106        BigInteger([5461406015399410446, 5014654494648953692, 8156709087178280082, 1299557346046566890]),
107    ];
108    #[rustfmt::skip]
109    const TWO_ADICITY: u32 = 47;
110    /// TWO_ADIC_ROOT_OF_UNITY = 8065159656716812877374967518403273466521432693661810619979959746626482506078
111    /// Encoded in Montgomery form, the value is
112    /// (8065159656716812877374967518403273466521432693661810619979959746626482506078 * R % q) =
113    /// 7039866554349711480672062101017509031917008525101396696252683426045173093960
114    #[rustfmt::skip]
115    const TWO_ADIC_ROOT_OF_UNITY: BigInteger = BigInteger([
116        12646347781564978760u64,
117        6783048705277173164u64,
118        268534165941069093u64,
119        1121515446318641358u64,
120    ]);
121}
122
123impl FieldParameters for FrParameters {
124    #[rustfmt::skip]
125    const CAPACITY: u32 = Self::MODULUS_BITS - 1;
126    /// GENERATOR = 22
127    /// Encoded in Montgomery form, so the value is
128    /// (22 * R) % q = 5642976643016801619665363617888466827793962762719196659561577942948671127251
129    #[rustfmt::skip]
130    const GENERATOR: BigInteger = BigInteger([
131        2984901390528151251u64,
132        10561528701063790279u64,
133        5476750214495080041u64,
134        898978044469942640u64,
135    ]);
136    #[rustfmt::skip]
137    const INV: u64 = 725501752471715839u64;
138    /// MODULUS = 8444461749428370424248824938781546531375899335154063827935233455917409239041
139    #[rustfmt::skip]
140    const MODULUS: BigInteger = BigInteger([
141        725501752471715841u64,
142        6461107452199829505u64,
143        6968279316240510977u64,
144        1345280370688173398u64,
145    ]);
146    #[rustfmt::skip]
147    const MODULUS_BITS: u32 = 253;
148    /// (r - 1)/2 =
149    /// 4222230874714185212124412469390773265687949667577031913967616727958704619520
150    #[rustfmt::skip]
151    const MODULUS_MINUS_ONE_DIV_TWO: BigInteger = BigInteger([
152        0x8508c00000000000,
153        0xacd53b7f68000000,
154        0x305a268f2e1bd800,
155        0x955b2af4d1652ab,
156    ]);
157    #[rustfmt::skip]
158    const R: BigInteger = BigInteger([
159        9015221291577245683u64,
160        8239323489949974514u64,
161        1646089257421115374u64,
162        958099254763297437u64,
163    ]);
164    #[rustfmt::skip]
165    const R2: BigInteger = BigInteger([
166        2726216793283724667u64,
167        14712177743343147295u64,
168        12091039717619697043u64,
169        81024008013859129u64,
170    ]);
171    #[rustfmt::skip]
172    const REPR_SHAVE_BITS: u32 = 3;
173    // T and T_MINUS_ONE_DIV_TWO, where r - 1 = 2^s * t
174
175    /// t = (r - 1) / 2^s =
176    /// 60001509534603559531609739528203892656505753216962260608619555
177    #[rustfmt::skip]
178    const T: BigInteger = BigInteger([
179        0xedfda00000021423,
180        0x9a3cb86f6002b354,
181        0xcabd34594aacc168,
182        0x2556,
183    ]);
184    /// (t - 1) / 2 =
185    /// 30000754767301779765804869764101946328252876608481130304309777
186    #[rustfmt::skip]
187    const T_MINUS_ONE_DIV_TWO: BigInteger = BigInteger([
188        0x76fed00000010a11,
189        0x4d1e5c37b00159aa,
190        0x655e9a2ca55660b4,
191        0x12ab,
192    ]);
193}
194
195impl PoseidonDefaultParameters for FrParameters {
196    const PARAMS_OPT_FOR_CONSTRAINTS: [PoseidonDefaultParametersEntry; 7] = [
197        PoseidonDefaultParametersEntry::new(2, 17, 8, 31, 0),
198        PoseidonDefaultParametersEntry::new(3, 17, 8, 31, 0),
199        PoseidonDefaultParametersEntry::new(4, 17, 8, 31, 0),
200        PoseidonDefaultParametersEntry::new(5, 17, 8, 31, 0),
201        PoseidonDefaultParametersEntry::new(6, 17, 8, 31, 0),
202        PoseidonDefaultParametersEntry::new(7, 17, 8, 31, 0),
203        PoseidonDefaultParametersEntry::new(8, 17, 8, 31, 0),
204    ];
205}
206
207#[cfg(test)]
208mod tests {
209    use super::*;
210    use snarkvm_fields::{FftField, Field, PrimeField};
211
212    #[test]
213    fn test_powers_of_root_of_unity() {
214        let two = Fr::from(2u8);
215
216        // Compute the expected powers of root of unity.
217        let root_of_unity = Fr::two_adic_root_of_unity();
218        let powers = (0..FrParameters::TWO_ADICITY - 1)
219            .map(|i| root_of_unity.pow(two.pow(Fr::from(i as u64).to_bigint()).to_bigint()))
220            .collect::<Vec<_>>();
221        assert_eq!(powers[0], Fr::two_adic_root_of_unity());
222
223        // Ensure the correct number of powers of root of unity are present.
224        assert_eq!(FrParameters::POWERS_OF_ROOTS_OF_UNITY.len() as u64, (FrParameters::TWO_ADICITY - 1) as u64);
225        assert_eq!(FrParameters::POWERS_OF_ROOTS_OF_UNITY.len(), powers.len());
226
227        // Ensure the expected and candidate powers match.
228        for (expected, candidate) in powers.iter().zip(FrParameters::POWERS_OF_ROOTS_OF_UNITY) {
229            // println!("BigInteger({:?}),", expected.0.0);
230            println!("{:?} =?= {:?}", expected.0, candidate);
231            assert_eq!(&expected.0, candidate);
232        }
233    }
234
235    #[test]
236    fn test_two_adic_root_of_unity() {
237        let expected = Fr::multiplicative_generator().pow(FrParameters::T);
238        assert_eq!(expected, Fr::two_adic_root_of_unity());
239    }
240}
snarkvm_curves/bls12_377/fr.rs

snarkvm_curves/bls12_377/
fr.rs
