fp/
fp_element.rs

1//! Base prime-field element $\mathbb{F}_p = \mathbb{Z} / p\mathbb{Z}$
2//! backed by `crypto-bigint`.
3
4use core::ops::{Add, Mul, Neg, Sub};
5use std::fmt;
6
7use crate::field_ops::{FieldFromRepr, FieldOps, FieldRandom};
8use crypto_bigint::{
9    modular::{ConstMontyForm, ConstPrimeMontyParams},
10    NonZero, RandomMod, Uint,
11};
12use subtle::{Choice, ConditionallySelectable, ConstantTimeEq, CtOption};
13
14/// An element of the prime field $\mathbb{F}_p =
15/// \mathbb{Z}/p\mathbb{Z}$, stored in Montgomery form.
16///
17/// The internal value uses `crypto-bigint`'s [`ConstMontyForm`], so arithmetic
18/// is performed in Montgomery representation while the public constructors and
19/// accessors accept and return canonical integers.
20#[derive(Debug, Clone, Copy, PartialEq, Eq)]
21pub struct FpElement<MOD, const LIMBS: usize>
22where
23    MOD: ConstPrimeMontyParams<LIMBS>,
24{
25    pub(crate) value: ConstMontyForm<MOD, LIMBS>,
26}
27
28// ---------------------------------------------------------------------------
29// Constructors / accessors
30// ---------------------------------------------------------------------------
31
32impl<MOD, const LIMBS: usize> FpElement<MOD, LIMBS>
33where
34    MOD: ConstPrimeMontyParams<LIMBS>,
35{
36    /// Goes from an `Uint<LIMBS>` to an element of $\mathbb{F}_p$
37    ///
38    /// # Arguments
39    ///
40    /// * `x` - An integer (type: `Uint<LIMBS>`)
41    ///
42    /// # Returns
43    ///
44    /// Element of $\mathbb{F}_p$ (type: `Self`)
45    pub fn from_uint(x: Uint<LIMBS>) -> Self {
46        Self {
47            value: ConstMontyForm::<MOD, LIMBS>::new(&x),
48        }
49    }
50
51    /// Goes from an `[u64; LIMBS]` to an element of $\mathbb{F}_p$
52    ///
53    /// # Arguments
54    ///
55    /// * `words` - A vec of `u64` (type: `[u64; LIMBS]`)
56    ///
57    /// # Returns
58    ///
59    /// Element of $\mathbb{F}_p$ (type: `Self`)
60    pub fn from_words(words: [u64; LIMBS]) -> Self {
61        Self::from_uint(Uint::<LIMBS>::from_words(words))
62    }
63
64    /// Goes from an `&[u64]` to an element of $\mathbb{F}_p$
65    ///
66    /// # Arguments
67    ///
68    /// * `limbs` - A vec of `u64` (type: `&[u64]`)
69    ///
70    /// # Returns
71    ///
72    /// Element of $\mathbb{F}_p$ (type: `Self`)
73    pub fn from_limbs(limbs: &[u64]) -> Self {
74        assert_eq!(limbs.len(), LIMBS, "wrong number of limbs");
75        let mut words = [0u64; LIMBS];
76        words.copy_from_slice(limbs);
77        Self::from_words(words)
78    }
79
80    /// Goes from an `u64` to an element of $\mathbb{F}_p$
81    ///
82    /// # Arguments
83    ///
84    /// * `val` - A `u64` int (type: `u64`)
85    ///
86    /// # Returns
87    ///
88    /// Element of $\mathbb{F}_p$ (type: `Self`)
89    pub fn from_u64(val: u64) -> Self {
90        Self::from_uint(Uint::<LIMBS>::from_u64(val))
91    }
92
93    /// Goes from an element of $\mathbb{F}_p$ to the corresponding `Uint`
94    ///
95    /// # Arguments
96    ///
97    /// * `&self` - Element of $\mathbb{F}_p$ (type: `Self`)
98    ///
99    /// # Returns
100    ///
101    /// The corresponding `Uint` (type: `Uint<LIMBS>`)
102    pub fn as_uint(&self) -> Uint<LIMBS> {
103        self.value.retrieve()
104    }
105
106    /// Goes from an element of $\mathbb{F}_p$ to the limbs
107    ///
108    /// # Arguments
109    ///
110    /// * `&self` - Element of $\mathbb{F}_p$ (type: `Self`)
111    ///
112    /// # Returns
113    ///
114    /// The limbs giving the integer (type: `[u64; LIMBS]`)
115    pub fn as_limbs(&self) -> [u64; LIMBS] {
116        self.value.retrieve().to_words()
117    }
118
119    /// Gives a montgomery `Uint<LIMBS>` from an $\mathbb{F}_p$
120    /// element
121    ///
122    /// # Arguments
123    ///
124    /// * `&self` - Element of $\mathbb{F}_p$ (type: `Self`)
125    ///
126    /// # Returns
127    ///
128    /// Integer in montgomery from (type: `Uint<LIMBS>`)
129    pub fn to_montgomery(&self) -> Uint<LIMBS> {
130        self.value.to_montgomery()
131    }
132
133    /// Gives an element of $\mathbb{F}_p$ from the Montgomery
134    /// representation.
135    ///
136    /// # Arguments
137    ///
138    /// * `mont` - The input montgomery value (type: `Uint<LIMBS>`)
139    ///
140    /// # Returns
141    ///
142    /// Corresponding element of $\mathbb{F}_p$ (type: `Self`)
143    pub fn from_montgomery(mont: Uint<LIMBS>) -> Self {
144        Self {
145            value: ConstMontyForm::<MOD, LIMBS>::from_montgomery(mont),
146        }
147    }
148}
149
150// ---------------------------------------------------------------------------
151// CtOption functionalities
152// ---------------------------------------------------------------------------
153
154impl<MOD, const LIMBS: usize> Default for FpElement<MOD, LIMBS>
155where
156    MOD: ConstPrimeMontyParams<LIMBS>,
157{
158    fn default() -> Self {
159        Self::zero()
160    }
161}
162
163impl<MOD, const LIMBS: usize> ConditionallySelectable for FpElement<MOD, LIMBS>
164where
165    MOD: ConstPrimeMontyParams<LIMBS>,
166{
167    fn conditional_select(a: &Self, b: &Self, choice: Choice) -> Self {
168        Self {
169            value: ConstMontyForm::conditional_select(&a.value, &b.value, choice),
170        }
171    }
172
173    fn conditional_assign(&mut self, other: &Self, choice: Choice) {
174        self.value.conditional_assign(&other.value, choice)
175    }
176
177    fn conditional_swap(a: &mut Self, b: &mut Self, choice: Choice) {
178        ConstMontyForm::conditional_swap(&mut a.value, &mut b.value, choice)
179    }
180}
181
182impl<MOD, const LIMBS: usize> ConstantTimeEq for FpElement<MOD, LIMBS>
183where
184    MOD: ConstPrimeMontyParams<LIMBS>,
185{
186    fn ct_eq(&self, other: &Self) -> Choice {
187        ConstMontyForm::ct_eq(&self.value, &other.value)
188    }
189
190    fn ct_ne(&self, other: &Self) -> Choice {
191        ConstMontyForm::ct_ne(&self.value, &other.value)
192    }
193}
194
195// ---------------------------------------------------------------------------
196// Operator overloads
197// ---------------------------------------------------------------------------
198
199impl<MOD, const LIMBS: usize> Add for FpElement<MOD, LIMBS>
200where
201    MOD: ConstPrimeMontyParams<LIMBS>,
202{
203    type Output = Self;
204    fn add(self, rhs: Self) -> Self {
205        Self {
206            value: self.value + rhs.value,
207        }
208    }
209}
210
211impl<MOD, const LIMBS: usize> Sub for FpElement<MOD, LIMBS>
212where
213    MOD: ConstPrimeMontyParams<LIMBS>,
214{
215    type Output = Self;
216    fn sub(self, rhs: Self) -> Self {
217        Self {
218            value: self.value - rhs.value,
219        }
220    }
221}
222
223impl<MOD, const LIMBS: usize> Mul for FpElement<MOD, LIMBS>
224where
225    MOD: ConstPrimeMontyParams<LIMBS>,
226{
227    type Output = Self;
228    fn mul(self, rhs: Self) -> Self {
229        Self {
230            value: self.value * rhs.value,
231        }
232    }
233}
234
235impl<MOD, const LIMBS: usize> Neg for FpElement<MOD, LIMBS>
236where
237    MOD: ConstPrimeMontyParams<LIMBS>,
238{
239    type Output = Self;
240    fn neg(self) -> Self {
241        Self { value: -self.value }
242    }
243}
244
245// ---------------------------------------------------------------------------
246// FieldOps
247// ---------------------------------------------------------------------------
248
249impl<MOD, const LIMBS: usize> FieldOps for FpElement<MOD, LIMBS>
250where
251    MOD: ConstPrimeMontyParams<LIMBS>,
252{
253    fn zero() -> Self {
254        Self {
255            value: ConstMontyForm::<MOD, LIMBS>::ZERO,
256        }
257    }
258    fn one() -> Self {
259        Self {
260            value: ConstMontyForm::<MOD, LIMBS>::ONE,
261        }
262    }
263
264    fn from_u64(x: u64) -> Self {
265        Self::from_u64(x)
266    }
267
268    fn is_zero(&self) -> Choice {
269        Self::ct_eq(self, &Self::zero())
270    }
271    fn is_one(&self) -> Choice {
272        Self::ct_eq(self, &Self::one())
273    }
274
275    fn negate(&self) -> Self {
276        Self { value: -self.value }
277    }
278    fn add(&self, rhs: &Self) -> Self {
279        Self {
280            value: self.value + rhs.value,
281        }
282    }
283    fn sub(&self, rhs: &Self) -> Self {
284        Self {
285            value: self.value - rhs.value,
286        }
287    }
288    fn mul(&self, rhs: &Self) -> Self {
289        Self {
290            value: self.value * rhs.value,
291        }
292    }
293    fn square(&self) -> Self {
294        Self {
295            value: self.value.square(),
296        }
297    }
298    fn double(&self) -> Self {
299        Self {
300            value: self.value.double(),
301        }
302    }
303
304    fn invert(&self) -> CtOption<Self> {
305        self.value.invert().map(|inv| Self { value: inv }).into()
306    }
307
308    fn frobenius(&self) -> Self {
309        *self
310    }
311    fn norm(&self) -> Self {
312        *self
313    }
314    fn trace(&self) -> Self {
315        *self
316    }
317
318    fn sqrt(&self) -> CtOption<Self> {
319        self.value.sqrt().map(|sqrt| Self { value: sqrt }).into()
320    }
321
322    fn legendre(&self) -> i8 {
323        i8::from(self.value.jacobi_symbol())
324    }
325
326    fn characteristic() -> Vec<u64> {
327        let minus_one = ConstMontyForm::<MOD, LIMBS>::ZERO - ConstMontyForm::<MOD, LIMBS>::ONE;
328        let p_minus_1: Uint<LIMBS> = minus_one.retrieve();
329        let p = p_minus_1.wrapping_add(&Uint::<LIMBS>::ONE);
330        p.to_words().to_vec()
331    }
332
333    fn degree() -> u32 {
334        1
335    }
336}
337
338// ---------------------------------------------------------------------------
339// Pretty Display
340// ---------------------------------------------------------------------------
341
342impl<MOD, const LIMBS: usize> fmt::Display for FpElement<MOD, LIMBS>
343where
344    MOD: ConstPrimeMontyParams<LIMBS>,
345{
346    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
347        let val = self.as_uint();
348        if LIMBS == 1 {
349            write!(f, "{}", val.to_words()[0])
350        } else {
351            write!(f, "0x{val:x}")
352        }
353    }
354}
355
356// ---------------------------------------------------------------------------
357// Cryptographically secure random sampling
358// ---------------------------------------------------------------------------
359
360impl<MOD, const LIMBS: usize> FieldRandom for FpElement<MOD, LIMBS>
361where
362    MOD: ConstPrimeMontyParams<LIMBS>,
363{
364    /// Sample a uniformly random element of Fp using a CSPRNG.
365    fn random(rng: &mut (impl rand::CryptoRng + rand::Rng)) -> Self {
366        let minus_one = ConstMontyForm::<MOD, LIMBS>::ZERO - ConstMontyForm::<MOD, LIMBS>::ONE;
367        let p_minus_1: Uint<LIMBS> = minus_one.retrieve();
368        let p = p_minus_1.wrapping_add(&Uint::<LIMBS>::ONE);
369        let modulus = NonZero::new(p).expect("prime modulus must be nonzero");
370        let val = Uint::<LIMBS>::random_mod_vartime(rng, &modulus);
371        Self::from_uint(val)
372    }
373}
374
375impl<MOD, const LIMBS: usize> FieldFromRepr for FpElement<MOD, LIMBS>
376where
377    MOD: ConstPrimeMontyParams<LIMBS>,
378{
379    type Repr = Uint<LIMBS>;
380
381    fn from_repr(x: Self::Repr) -> Self {
382        Self::from_uint(x)
383    }
384}
fp/fp_element.rs

fp/
fp_element.rs
