decaf377/fields/
fq.rs

1use cfg_if::cfg_if;
2use rand_core::CryptoRngCore;
3
4use crate::EncodingError;
5
6#[cfg(feature = "arkworks")]
7pub mod arkworks;
8mod ops;
9mod u32;
10
11// The u64 backend requires arkworks
12#[cfg(feature = "arkworks")]
13mod u64;
14
15cfg_if! {
16    if #[cfg(feature = "arkworks")] {
17        pub type Fq = u64::Fq;
18    } else {
19        pub type Fq = u32::Fq;
20    }
21}
22
23const B: usize = 253;
24const N_8: usize = (B + 7) / 8;
25const N_32: usize = (B + 31) / 32;
26const N_64: usize = (B + 63) / 64;
27
28impl Fq {
29    pub const MODULUS_LIMBS: [u64; N_64] = [
30        725501752471715841,
31        6461107452199829505,
32        6968279316240510977,
33        1345280370688173398,
34    ];
35
36    pub const MODULUS_MINUS_ONE_DIV_TWO_LIMBS: [u64; N_64] = [
37        9586122913090633728,
38        12453925762954690560,
39        3484139658120255488,
40        672640185344086699,
41    ];
42
43    pub const MODULUS_BIT_SIZE: u32 = 0xfd;
44
45    pub const TRACE_LIMBS: [u64; N_64] = [
46        17149038877957297187,
47        11113960768935211860,
48        14608890324369326440,
49        9558,
50    ];
51
52    pub const TRACE_MINUS_ONE_DIV_TWO_LIMBS: [u64; N_64] = [
53        8574519438978648593,
54        5556980384467605930,
55        7304445162184663220,
56        4779,
57    ];
58
59    // c1
60    pub const TWO_ADICITY: u32 = 0x2f;
61
62    pub const QUADRATIC_NON_RESIDUE_TO_TRACE: Self = Self::from_montgomery_limbs([
63        4340692304772210610,
64        11102725085307959083,
65        15540458298643990566,
66        944526744080888988,
67    ]);
68
69    pub const MULTIPLICATIVE_GENERATOR: Self = Self::from_montgomery_limbs([
70        2984901390528151251,
71        10561528701063790279,
72        5476750214495080041,
73        898978044469942640,
74    ]);
75
76    pub const TWO_ADIC_ROOT_OF_UNITY: Self = Self::from_montgomery_limbs([
77        12646347781564978760,
78        6783048705277173164,
79        268534165941069093,
80        1121515446318641358,
81    ]);
82
83    pub const FIELD_SIZE_POWER_OF_TWO: Self = Self::from_montgomery_limbs([
84        2726216793283724667,
85        14712177743343147295,
86        12091039717619697043,
87        81024008013859129,
88    ]);
89
90    pub fn from_le_bytes_mod_order(bytes: &[u8]) -> Self {
91        bytes
92            .chunks(N_8)
93            .map(|x| {
94                let mut padded = [0u8; N_8];
95                padded[..x.len()].copy_from_slice(x);
96                Self::from_raw_bytes(&padded)
97            }) // [X, 2^(256) * X, ...]
98            .rev()
99            .fold(Self::ZERO, |acc, x| {
100                acc * (Self::FIELD_SIZE_POWER_OF_TWO) + x
101            }) // let acc =
102    }
103
104    /// Convert bytes into an Fq element, returning None if these bytes are not already reduced.
105    ///
106    /// This means that values that cannot be produced by encoding a field element will return
107    /// None, enforcing canonical serialization.
108    pub fn from_bytes_checked(bytes: &[u8; N_8]) -> Result<Self, EncodingError> {
109        let reduced = Self::from_raw_bytes(bytes);
110        if reduced.to_bytes_le() == *bytes {
111            Ok(reduced)
112        } else {
113            Err(EncodingError::InvalidEncoding)
114        }
115    }
116
117    pub fn to_bytes(&self) -> [u8; N_8] {
118        self.to_bytes_le()
119    }
120
121    /// Sample a random field element uniformly.
122    pub fn rand<R: CryptoRngCore>(rng: &mut R) -> Self {
123        // Sample wide, reduce
124        let bytes = {
125            let mut out = [0u8; N_8 + 16];
126            rng.fill_bytes(&mut out);
127            out
128        };
129        Self::from_le_bytes_mod_order(&bytes)
130    }
131
132    /// Raise this element to a given power.
133    ///
134    /// Note: Arkworks provides another method for this, called `pow`.
135    pub fn power<S: AsRef<[u64]>>(&self, exp: S) -> Self {
136        let mut res = Fq::from(1u64);
137        let exp_u64 = exp.as_ref();
138        for _ in 0..exp_u64[0] {
139            res *= self;
140        }
141        res
142    }
143}
144
145#[cfg(test)]
146mod test {
147    use super::*;
148
149    #[test]
150    fn test_from_bytes_checked() {
151        assert_eq!(Fq::from_bytes_checked(&[0; N_8]), Ok(Fq::ZERO));
152        assert!(Fq::from_bytes_checked(&[0xFF; N_8]).is_err());
153    }
154}
decaf377/fields/fq.rs

decaf377/fields/
fq.rs
