fp/prime/
primes_generic.rs

1use std::str::FromStr;
2
3use super::*;
4
5def_prime_static!(P2, 2);
6def_prime_static!(P3, 3);
7def_prime_static!(P5, 5);
8def_prime_static!(P7, 7);
9
10impl_prime_ops!(P2);
11impl_prime_ops!(P3);
12impl_prime_ops!(P5);
13impl_prime_ops!(P7);
14
15impl_try_from!(P2);
16impl_try_from!(P3);
17impl_try_from!(P5);
18impl_try_from!(P7);
19
20pub(crate) mod fp {
21    use super::{P2, P3, P5, P7};
22    use crate::field::Fp;
23
24    pub const F2: Fp<P2> = Fp::new(P2);
25    pub const F3: Fp<P3> = Fp::new(P3);
26    pub const F5: Fp<P5> = Fp::new(P5);
27    pub const F7: Fp<P7> = Fp::new(P7);
28}
29
30#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
31pub struct ValidPrime {
32    p: u32,
33}
34
35pub const fn is_prime(p: u32) -> bool {
36    // (2..p).all(|k| p % k != 0), but make it const
37    let mut k = 2;
38    while k < p {
39        if p.is_multiple_of(k) {
40            return false;
41        }
42        k += 1;
43    }
44    true
45}
46
47impl ValidPrime {
48    pub const fn new(p: u32) -> Self {
49        // We need the size restriction for a few reasons.
50        //
51        // First, we need `bit_length(p)` to be smaller than 64. Otherwise, shifting a u64 by 64
52        // bits is considered an overflow. We could special case these shifts to be setting to
53        // 0, but that doesn't seem worth it.
54        //
55        // More importantly, the existence of `Prime::as_i32` means that we need `p` to fit in
56        // an i32. We want this method because there are a few places in the codebase that
57        // use it. It might be possible to go and change all of those to use `as_u32` instead,
58        // but it doesn't seem worth it for now.
59        assert!(p < (1 << 31), "Tried to construct a prime larger than 2^31");
60        assert!(is_prime(p), "Tried to construct a composite dynamic prime");
61        Self { p }
62    }
63
64    pub const fn new_unchecked(p: u32) -> Self {
65        Self { p }
66    }
67}
68
69impl Prime for ValidPrime {
70    fn as_i32(self) -> i32 {
71        self.p as i32
72    }
73
74    fn to_dyn(self) -> Self {
75        self
76    }
77}
78
79impl_prime_ops!(ValidPrime);
80
81impl TryFrom<u32> for ValidPrime {
82    type Error = PrimeError;
83
84    fn try_from(p: u32) -> Result<Self, PrimeError> {
85        if is_prime(p) {
86            Ok(Self { p })
87        } else {
88            Err(PrimeError::InvalidPrime(p))
89        }
90    }
91}
92
93impl FromStr for ValidPrime {
94    type Err = PrimeError;
95
96    fn from_str(s: &str) -> Result<Self, Self::Err> {
97        let p: u32 = s.parse().map_err(PrimeError::NotAnInteger)?;
98        Self::try_from(p)
99    }
100}
101
102impl Serialize for ValidPrime {
103    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
104    where
105        S: Serializer,
106    {
107        self.as_u32().serialize(serializer)
108    }
109}
110
111impl<'de> Deserialize<'de> for ValidPrime {
112    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
113    where
114        D: Deserializer<'de>,
115    {
116        let p: u32 = u32::deserialize(deserializer)?;
117        Self::try_from(p).map_err(D::Error::custom)
118    }
119}
120
121#[cfg(feature = "proptest")]
122impl proptest::arbitrary::Arbitrary for ValidPrime {
123    type Parameters = Option<std::num::NonZeroU32>;
124    type Strategy = proptest::sample::Select<Self>;
125
126    /// An arbitrary `ValidPrime` in the range `2..(1 << 24)`, plus the largest prime that we
127    /// support. If `max` is specified, the primes are restricted to be less than `max`.
128    fn arbitrary_with(max: Self::Parameters) -> Self::Strategy {
129        use std::sync::OnceLock;
130
131        static TEST_PRIMES: OnceLock<Vec<ValidPrime>> = OnceLock::new();
132        let test_primes = TEST_PRIMES.get_or_init(|| {
133            // Sieve of Eratosthenes
134            const MAX: usize = 1 << 24;
135            let mut is_prime = Vec::new();
136            is_prime.resize_with(MAX, || true);
137            is_prime[0] = false;
138            is_prime[1] = false;
139            for i in 2..MAX {
140                if is_prime[i] {
141                    for j in ((2 * i)..MAX).step_by(i) {
142                        is_prime[j] = false;
143                    }
144                }
145            }
146            (0..MAX)
147                .filter(|&i| is_prime[i])
148                .map(|p| Self::new_unchecked(p as u32))
149                .chain(std::iter::once(Self::new_unchecked(2147483647)))
150                .collect()
151        });
152        let restricted_slice = if let Some(max) = max {
153            let max_index = test_primes
154                .iter()
155                .position(|&p| p >= max.get())
156                .unwrap_or(test_primes.len());
157
158            &test_primes[..max_index]
159        } else {
160            test_primes
161        };
162        proptest::sample::select(restricted_slice)
163    }
164}
165
166impl crate::MaybeArbitrary<Option<NonZeroU32>> for ValidPrime {}
fp/prime/primes_generic.rs

fp/prime/
primes_generic.rs
