ff_uint/ff/
traits.rs

1use crate::traits::Borsh;
2use crate::Uint;
3use crate::{BitIterBE, BitIteratorBE};
4
5pub trait PrimeFieldParams {
6    type Inner: Uint;
7    const MODULUS: Self::Inner;
8    const MODULUS_BITS: u32;
9    const REPR_SHAVE_BITS: u32;
10    const R: Self::Inner;
11    const R2: Self::Inner;
12    const INV: u64;
13    const GENERATOR: Self::Inner;
14    const S: u32;
15    const ROOT_OF_UNITY: Self::Inner;
16}
17
18#[derive(Debug, PartialEq)]
19pub enum LegendreSymbol {
20    Zero = 0,
21    QuadraticResidue = 1,
22    QuadraticNonResidue = -1,
23}
24
25pub trait Field:
26    Sized
27    + Clone
28    + Copy
29    + Default
30    + core::cmp::PartialEq
31    + core::cmp::Eq
32    + core::fmt::Debug
33    + core::fmt::Display
34{
35    const ZERO: Self;
36    const ONE: Self;
37
38    #[cfg(feature = "rand_support")]
39    fn random<R: rand::Rng + ?Sized>(rng: &mut R) -> Self;
40    fn is_zero(&self) -> bool;
41
42    fn wrapping_add(self, other: Self) -> Self;
43    fn wrapping_sub(self, other: Self) -> Self;
44    fn wrapping_mul(self, other: Self) -> Self;
45    fn wrapping_div(self, other: Self) -> Self {
46        self.wrapping_mul(other.checked_inv().expect("Division by zero"))
47    }
48    fn wrapping_neg(self) -> Self;
49    fn square(self) -> Self;
50    fn double(self) -> Self;
51    fn checked_inv(self) -> Option<Self>;
52
53    fn frobenius_map(self, power: usize) -> Self;
54
55    fn pow<S: BitIterBE>(self, exp: S) -> Self {
56        let mut res = Self::ONE;
57        let mut found_one = false;
58        for i in exp.bit_iter_be() {
59            if found_one {
60                res = res.square();
61            } else {
62                found_one = i;
63            }
64            if i {
65                res = res.wrapping_mul(self);
66            }
67        }
68        res
69    }
70}
71
72pub trait SqrtField: Field {
73    fn legendre(&self) -> LegendreSymbol;
74    fn sqrt(&self) -> Option<Self>;
75}
76
77pub trait PrimeField:
78    PrimeFieldParams + SqrtField + core::str::FromStr + From<&'static str> + Borsh
79{
80    fn from_uint(v: Self::Inner) -> Option<Self>;
81    fn from_mont_uint(v: Self::Inner) -> Option<Self>;
82    fn from_uint_unchecked(v: Self::Inner) -> Self;
83    fn from_mont_uint_unchecked(v: Self::Inner) -> Self;
84
85    fn to_uint(&self) -> Self::Inner;
86    fn to_mont_uint(&self) -> Self::Inner;
87    fn as_mont_uint(&self) -> &Self::Inner;
88    fn as_mont_uint_mut(&mut self) -> &mut Self::Inner;
89
90    fn to_other<Fq: PrimeField>(&self) -> Option<Fq> {
91        let u = self.to_uint().to_other()?;
92
93        if u >= Fq::MODULUS {
94            None
95        } else {
96            Some(Fq::from_uint_unchecked(u))
97        }
98    }
99
100    fn to_other_reduced<Fq: PrimeField>(&self) -> Fq {
101        match self.to_uint().to_other::<Fq::Inner>() {
102            Some(u) => Fq::from_uint_unchecked(u.wrapping_rem(Fq::MODULUS)),
103            None => {
104                let u = self
105                    .to_uint()
106                    .wrapping_rem(<Fq as PrimeFieldParams>::MODULUS.to_other().unwrap());
107                Fq::from_uint_unchecked(u.to_other().unwrap())
108            }
109        }
110    }
111}
ff_uint/ff/traits.rs

ff_uint/ff/
traits.rs
