substrate_bn/fields/
fp.rs

Help
1use alloc::vec::Vec;
2use core::ops::{Add, Mul, Neg, Sub};
3use rand::Rng;
4use crate::fields::FieldElement;
5use crate::arith::{U256, U512};
6
7macro_rules! field_impl {
8    ($name:ident, $modulus:expr, $rsquared:expr, $rcubed:expr, $one:expr, $inv:expr) => {
9        #[derive(Copy, Clone, PartialEq, Eq, Debug)]
10        #[repr(C)]
11        pub struct $name(U256);
12
13        impl From<$name> for U256 {
14            #[inline]
15            fn from(mut a: $name) -> Self {
16                a.0.mul(&U256::one(), &U256::from($modulus), $inv);
17
18                a.0
19            }
20        }
21
22        impl $name {
23            pub fn from_str(s: &str) -> Option<Self> {
24                let ints: Vec<_> = {
25                    let mut acc = Self::zero();
26                    (0..11).map(|_| {let tmp = acc; acc = acc + Self::one(); tmp}).collect()
27                };
28
29                let mut res = Self::zero();
30                for c in s.chars() {
31                    match c.to_digit(10) {
32                        Some(d) => {
33                            res = res * ints[10];
34                            res = res + ints[d as usize];
35                        },
36                        None => {
37                            return None;
38                        }
39                    }
40                }
41
42                Some(res)
43            }
44
45            /// Converts a U256 to an Fp so long as it's below the modulus.
46            pub fn new(mut a: U256) -> Option<Self> {
47                if a < U256::from($modulus) {
48                    a.mul(&U256::from($rsquared), &U256::from($modulus), $inv);
49
50                    Some($name(a))
51                } else {
52                    None
53                }
54            }
55
56            /// Converts a U256 to an Fr regardless of modulus.
57            pub fn new_mul_factor(mut a: U256) -> Self {
58                a.mul(&U256::from($rsquared), &U256::from($modulus), $inv);
59                $name(a)
60            }
61
62            pub fn interpret(buf: &[u8; 64]) -> Self {
63                $name::new(U512::interpret(buf).divrem(&U256::from($modulus)).1).unwrap()
64            }
65
66            /// Returns the modulus
67            #[inline]
68            #[allow(dead_code)]
69            pub fn modulus() -> U256 {
70                U256::from($modulus)
71            }
72
73            #[inline]
74            #[allow(dead_code)]
75            pub fn inv(&self) -> u128 {
76                $inv
77            }
78
79            pub fn raw(&self) -> &U256 {
80                &self.0
81            }
82
83            pub fn set_bit(&mut self, bit: usize, to: bool) {
84                self.0.set_bit(bit, to);
85            }
86        }
87
88        impl FieldElement for $name {
89            #[inline]
90            fn zero() -> Self {
91                $name(U256::from([0, 0, 0, 0]))
92            }
93
94            #[inline]
95            fn one() -> Self {
96                $name(U256::from($one))
97            }
98
99            fn random<R: Rng>(rng: &mut R) -> Self {
100                $name(U256::random(rng, &U256::from($modulus)))
101            }
102
103            #[inline]
104            fn is_zero(&self) -> bool {
105                self.0.is_zero()
106            }
107
108            fn inverse(mut self) -> Option<Self> {
109                if self.is_zero() {
110                    None
111                } else {
112                    self.0.invert(&U256::from($modulus));
113                    self.0.mul(&U256::from($rcubed), &U256::from($modulus), $inv);
114
115                    Some(self)
116                }
117            }
118        }
119
120        impl Add for $name {
121            type Output = $name;
122
123            #[inline]
124            fn add(mut self, other: $name) -> $name {
125                self.0.add(&other.0, &U256::from($modulus));
126
127                self
128            }
129        }
130
131        impl Sub for $name {
132            type Output = $name;
133
134            #[inline]
135            fn sub(mut self, other: $name) -> $name {
136                self.0.sub(&other.0, &U256::from($modulus));
137
138                self
139            }
140        }
141
142        impl Mul for $name {
143            type Output = $name;
144
145            #[inline]
146            fn mul(mut self, other: $name) -> $name {
147                self.0.mul(&other.0, &U256::from($modulus), $inv);
148
149                self
150            }
151        }
152
153        impl Neg for $name {
154            type Output = $name;
155
156            #[inline]
157            fn neg(mut self) -> $name {
158                self.0.neg(&U256::from($modulus));
159
160                self
161            }
162        }
163    }
164}
165
166field_impl!(
167    Fr,
168    [
169        0x43e1f593f0000001,
170        0x2833e84879b97091,
171        0xb85045b68181585d,
172        0x30644e72e131a029
173    ],
174    [
175        0x1bb8e645ae216da7,
176        0x53fe3ab1e35c59e3,
177        0x8c49833d53bb8085,
178        0x0216d0b17f4e44a5
179    ],
180    [
181        0x5e94d8e1b4bf0040,
182        0x2a489cbe1cfbb6b8,
183        0x893cc664a19fcfed,
184        0x0cf8594b7fcc657c
185    ],
186    [
187        0xac96341c4ffffffb,
188        0x36fc76959f60cd29,
189        0x666ea36f7879462e,
190        0xe0a77c19a07df2f
191    ],
192    0x6586864b4c6911b3c2e1f593efffffff
193);
194
195field_impl!(
196    Fq,
197    [
198        0x3c208c16d87cfd47,
199        0x97816a916871ca8d,
200        0xb85045b68181585d,
201        0x30644e72e131a029
202    ],
203    [
204        0xf32cfc5b538afa89,
205        0xb5e71911d44501fb,
206        0x47ab1eff0a417ff6,
207        0x06d89f71cab8351f
208    ],
209    [
210        0xb1cd6dafda1530df,
211        0x62f210e6a7283db6,
212        0xef7f0b0c0ada0afb,
213        0x20fd6e902d592544
214    ],
215    [
216        0xd35d438dc58f0d9d,
217        0xa78eb28f5c70b3d,
218        0x666ea36f7879462c,
219        0xe0a77c19a07df2f
220    ],
221    0x9ede7d651eca6ac987d20782e4866389
222);
223
224lazy_static::lazy_static! {
225
226    static ref FQ: U256 = U256::from([
227        0x3c208c16d87cfd47,
228        0x97816a916871ca8d,
229        0xb85045b68181585d,
230        0x30644e72e131a029
231    ]);
232
233	pub static ref FQ_MINUS3_DIV4: Fq =
234		Fq::new(3.into()).expect("3 is a valid field element and static; qed").neg() *
235		Fq::new(4.into()).expect("4 is a valid field element and static; qed").inverse()
236			.expect("4 has inverse in Fq and is static; qed");
237
238	static ref FQ_MINUS1_DIV2: Fq =
239		Fq::new(1.into()).expect("1 is a valid field element and static; qed").neg() *
240		Fq::new(2.into()).expect("2 is a valid field element and static; qed").inverse()
241			.expect("2 has inverse in Fq and is static; qed");
242
243}
244
245impl Fq {
246    pub fn sqrt(&self) -> Option<Self> {
247        let a1 = self.pow(*FQ_MINUS3_DIV4);
248        let a1a = a1 * *self;
249        let a0 = a1 * (a1a);
250
251        let mut am1 = *FQ;
252        am1.sub(&1.into(), &*FQ);
253
254        if a0 == Fq::new(am1).unwrap() {
255            None
256        } else {
257            Some(a1a)
258        }
259    }
260}
261
262#[inline]
263pub fn const_fq(i: [u64; 4]) -> Fq {
264    Fq(U256::from(i))
265}
266
267#[test]
268fn test_rsquared() {
269    let rng = &mut ::rand::thread_rng();
270
271    for _ in 0..1000 {
272        let a = Fr::random(rng);
273        let b: U256 = a.into();
274        let c = Fr::new(b).unwrap();
275
276        assert_eq!(a, c);
277    }
278
279    for _ in 0..1000 {
280        let a = Fq::random(rng);
281        let b: U256 = a.into();
282        let c = Fq::new(b).unwrap();
283
284        assert_eq!(a, c);
285    }
286}
287
288
289#[test]
290fn sqrt_fq() {
291    // from zcash test_proof.cpp
292    let fq1 = Fq::from_str("5204065062716160319596273903996315000119019512886596366359652578430118331601").unwrap();
293    let fq2 = Fq::from_str("348579348568").unwrap();
294
295    assert_eq!(fq1, fq2.sqrt().expect("348579348568 is quadratic residue"));
296}
substrate_bn/fields/fp.rs

substrate_bn/fields/
fp.rs
