fp/field/
fp.rs

1use serde::{Deserialize, Serialize};
2
3use super::{
4    Field,
5    element::{FieldElement, FieldElementContainer},
6    field_internal::FieldInternal,
7};
8// Reexport the prime fields in a more logical place
9pub use crate::prime::fp::*;
10use crate::{constants::BITS_PER_LIMB, limb::Limb, prime::Prime};
11
12/// A prime field. This is just a wrapper around a prime.
13#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash, Serialize, Deserialize)]
14pub struct Fp<P> {
15    p: P,
16}
17
18impl<P: Prime> Fp<P> {
19    pub const fn new(p: P) -> Self {
20        Self { p }
21    }
22
23    pub fn element(&self, value: u32) -> FieldElement<Self> {
24        self.el(value)
25    }
26}
27
28impl<P: Prime> Field for Fp<P> {
29    type Characteristic = P;
30
31    fn characteristic(self) -> Self::Characteristic {
32        self.p
33    }
34
35    fn degree(self) -> u32 {
36        1
37    }
38
39    fn zero(self) -> FieldElement<Self> {
40        self.el(0)
41    }
42
43    fn one(self) -> FieldElement<Self> {
44        self.el(1)
45    }
46
47    #[cfg(feature = "proptest")]
48    fn arb_element(self) -> impl proptest::strategy::Strategy<Value = FieldElement<Self>> {
49        use proptest::prelude::*;
50
51        (0..self.characteristic().as_u32()).prop_map(move |v| self.element(v))
52    }
53}
54
55impl<P: Prime> FieldInternal for Fp<P> {
56    type ElementContainer = u32;
57
58    fn el(self, value: Self::ElementContainer) -> FieldElement<Self> {
59        FieldElement::new(self, value % self.p.as_u32())
60    }
61
62    fn add_assign(self, a: &mut FieldElement<Self>, b: FieldElement<Self>) {
63        a.value = self.p.sum(**a, *b);
64    }
65
66    fn mul_assign(self, a: &mut FieldElement<Self>, b: FieldElement<Self>) {
67        a.value = self.p.product(**a, *b);
68    }
69
70    fn inv(self, a: FieldElement<Self>) -> Option<FieldElement<Self>> {
71        if *a == 0 {
72            None
73        } else {
74            Some(self.el(crate::prime::inverse(self.p, *a)))
75        }
76    }
77
78    fn neg(self, a: FieldElement<Self>) -> FieldElement<Self> {
79        self.el(if *a == 0 { 0 } else { self.p.as_u32() - *a })
80    }
81
82    fn frobenius(self, a: FieldElement<Self>) -> FieldElement<Self> {
83        a
84    }
85
86    fn encode(self, element: FieldElement<Self>) -> Limb {
87        element.value as Limb
88    }
89
90    fn decode(self, element: Limb) -> FieldElement<Self> {
91        // We have to pass in the already reduced value to `Self::el` because we have no guarantee
92        // that this Limb fits in a u32. For example, `element` could be the result of `fma_limb(0,
93        // 1_000_000, 1_000_000)`, if the prime is large enough.
94        let prime_limb = self.p.as_u32() as Limb;
95        self.el((element % prime_limb) as u32)
96    }
97
98    fn bit_length(self) -> usize {
99        let p = self.characteristic().as_u32() as u64;
100        match p {
101            // 2 is a special case b/c bitwise xor does the add and reduce together so we only need enough bits to fit p-1.
102            2 => 1,
103            _ => (BITS_PER_LIMB as u32 - (p * (p - 1)).leading_zeros()) as usize,
104        }
105    }
106
107    fn fma_limb(self, limb_a: Limb, limb_b: Limb, coeff: FieldElement<Self>) -> Limb {
108        if self.characteristic() == 2 {
109            limb_a ^ (coeff.value as Limb * limb_b)
110        } else {
111            limb_a + (coeff.value as Limb) * limb_b
112        }
113    }
114
115    /// Contributed by Robert Burklund.
116    fn reduce(self, limb: Limb) -> Limb {
117        match self.characteristic().as_u32() {
118            2 => limb,
119            3 => {
120                // Set top bit to 1 in every limb
121                const TOP_BIT: Limb = (!0 / 7) << (2 - BITS_PER_LIMB % 3);
122                let mut limb_2 = ((limb & TOP_BIT) >> 2) + (limb & (!TOP_BIT));
123                let mut limb_3s = limb_2 & (limb_2 >> 1);
124                limb_3s |= limb_3s << 1;
125                limb_2 ^= limb_3s;
126                limb_2
127            }
128            5 => {
129                // Set bottom bit to 1 in every limb
130                const BOTTOM_BIT: Limb = (!0 / 31) >> (BITS_PER_LIMB % 5);
131                const BOTTOM_TWO_BITS: Limb = BOTTOM_BIT | (BOTTOM_BIT << 1);
132                const BOTTOM_THREE_BITS: Limb = BOTTOM_BIT | (BOTTOM_TWO_BITS << 1);
133                let a = (limb >> 2) & BOTTOM_THREE_BITS;
134                let b = limb & BOTTOM_TWO_BITS;
135                let m = (BOTTOM_BIT << 3) - a + b;
136                let mut c = (m >> 3) & BOTTOM_BIT;
137                c |= c << 1;
138                let d = m & BOTTOM_THREE_BITS;
139                d + c - BOTTOM_TWO_BITS
140            }
141            // Slow generic fallback. If anyone cares enough about some larger prime, they can add a faster implementation
142            _ => self.pack(self.unpack(limb)),
143        }
144    }
145}
146
147#[cfg(feature = "proptest")]
148impl<P: Prime> proptest::arbitrary::Arbitrary for Fp<P> {
149    type Parameters = ();
150    type Strategy = proptest::strategy::BoxedStrategy<Self>;
151
152    fn arbitrary_with(_args: Self::Parameters) -> Self::Strategy {
153        use proptest::prelude::*;
154
155        any::<P>().prop_map(Self::new).boxed()
156    }
157}
158
159impl<P: Prime> crate::MaybeArbitrary<()> for Fp<P> {}
160
161impl<P> std::ops::Deref for Fp<P> {
162    type Target = P;
163
164    fn deref(&self) -> &Self::Target {
165        &self.p
166    }
167}
168
169impl<P: Prime> From<P> for Fp<P> {
170    fn from(p: P) -> Self {
171        Self { p }
172    }
173}
174
175impl FieldElementContainer for u32 {}
176
177impl<P: Prime> From<FieldElement<Fp<P>>> for u32 {
178    fn from(element: FieldElement<Fp<P>>) -> Self {
179        element.value
180    }
181}
182
183#[cfg(test)]
184mod tests {
185    use super::Fp;
186    use crate::field::tests::field_tests;
187
188    mod validprime {
189        use super::*;
190        use crate::prime::ValidPrime;
191
192        field_tests!(Fp<ValidPrime>);
193    }
194
195    macro_rules! static_fp_tests {
196        ($p:tt) => {
197            paste::paste! {
198                static_fp_tests!(@ [<$p:lower>], $p, $p);
199            }
200        };
201        (@ $mod_name:ident, $p_ident:ident, $p_ty:ty) => {
202            mod $mod_name {
203                use super::*;
204                use crate::prime::$p_ident;
205
206                field_tests!(Fp<$p_ty>);
207            }
208        };
209    }
210
211    static_fp_tests!(P2);
212    cfg_if::cfg_if! { if #[cfg(feature = "odd-primes")] {
213        static_fp_tests!(P3);
214        static_fp_tests!(P5);
215        static_fp_tests!(P7);
216    }}
217}
fp/field/fp.rs

fp/field/
fp.rs
