num_prime/
rand.rs

1use crate::mint::SmallMint;
2use crate::nt_funcs::{is_prime, is_prime64, next_prime};
3use crate::{PrimalityTestConfig, RandPrime};
4#[cfg(feature = "num-bigint")]
5use num_bigint::{BigUint, RandBigInt};
6use rand::Rng;
7
8macro_rules! impl_randprime_prim {
9    ($($T:ty)*) => {$(
10        impl<R: Rng> RandPrime<$T> for R {
11            #[inline]
12            fn gen_prime(&mut self, bit_size: usize, _: Option<PrimalityTestConfig>) -> $T {
13                if bit_size > (<$T>::BITS as usize) {
14                    panic!("The given bit size limit exceeded the capacity of the integer type!")
15                }
16
17                loop {
18                    let t: $T = self.gen();
19                    let t = (t >> (<$T>::BITS - bit_size as u32)) | 1; // filter even numbers
20                    if is_prime64(t as u64) {
21                        break t
22                    } else if let Some(p) = next_prime(&t, None) {
23                        // deterministic primality test will be used for integers under u64
24                        break p
25                    }
26                }
27            }
28
29            #[inline]
30            fn gen_prime_exact(&mut self, bit_size: usize, _: Option<PrimalityTestConfig>) -> $T {
31                if bit_size > (<$T>::BITS as usize) {
32                    panic!("The given bit size limit exceeded the capacity of the integer type!")
33                }
34
35                loop {
36                    let t: $T = self.gen();
37                    let t = (t >> (<$T>::BITS - bit_size as u32)) | 1 | (1 << (bit_size - 1));
38                    if is_prime64(t as u64) {
39                        break t
40                    } else if let Some(p) = next_prime(&t, None) {
41                        // deterministic primality test will be used for integers under u64
42                        break p
43                    }
44                }
45            }
46
47            #[inline]
48            fn gen_safe_prime(&mut self, bit_size: usize) -> $T {
49                loop {
50                    // deterministic primality test will be used for integers under u64
51                    let p = self.gen_prime(bit_size, None);
52
53                    // test (p-1)/2
54                    if is_prime64((p >> 1) as u64) {
55                        break p
56                    }
57                    // test 2p+1
58                    if let Some(p2) = p.checked_mul(2).and_then(|v| v.checked_add(1)) {
59                        if is_prime64(p2 as u64) {
60                            break p2
61                        }
62                    }
63                }
64            }
65
66            #[inline]
67            fn gen_safe_prime_exact(&mut self, bit_size: usize) -> $T {
68                loop {
69                    // deterministic primality test will be used for integers under u64
70                    let p: $T = self.gen_prime_exact(bit_size, None);
71
72                    // test (p-1)/2
73                    if is_prime64((p >> 1) as u64) {
74                        break p
75                    }
76                }
77            }
78        }
79    )*}
80}
81impl_randprime_prim!(u8 u16 u32 u64);
82
83impl<R: Rng> RandPrime<u128> for R {
84    #[inline]
85    fn gen_prime(&mut self, bit_size: usize, config: Option<PrimalityTestConfig>) -> u128 {
86        assert!(
87            bit_size <= (u128::BITS as usize),
88            "The given bit size limit exceeded the capacity of the integer type!"
89        );
90
91        loop {
92            let t: u128 = self.gen();
93            let t = (t >> (u128::BITS - bit_size as u32)) | 1; // filter even numbers
94            if is_prime(&SmallMint::from(t), config).probably() {
95                break t;
96            } else if let Some(p) = next_prime(&t, None) {
97                // deterministic primality test will be used for integers under u64
98                break p;
99            }
100        }
101    }
102
103    #[inline]
104    fn gen_prime_exact(&mut self, bit_size: usize, config: Option<PrimalityTestConfig>) -> u128 {
105        assert!(
106            bit_size <= (u128::BITS as usize),
107            "The given bit size limit exceeded the capacity of the integer type!"
108        );
109
110        loop {
111            let t: u128 = self.gen();
112            let t = (t >> (u128::BITS - bit_size as u32)) | 1 | (1 << (bit_size - 1));
113            if is_prime(&SmallMint::from(t), config).probably() {
114                break t;
115            } else if let Some(p) = next_prime(&t, None) {
116                // deterministic primality test will be used for integers under u64
117                break p;
118            }
119        }
120    }
121
122    #[inline]
123    fn gen_safe_prime(&mut self, bit_size: usize) -> u128 {
124        loop {
125            let config = Some(PrimalityTestConfig::strict());
126            let p = self.gen_prime(bit_size, config);
127            if is_prime(&SmallMint::from(p >> 1), config).probably() {
128                break p;
129            }
130            if let Some(p2) = p.checked_mul(2).and_then(|v| v.checked_add(1)) {
131                if is_prime(&p2, config).probably() {
132                    break p2;
133                }
134            }
135        }
136    }
137
138    #[inline]
139    fn gen_safe_prime_exact(&mut self, bit_size: usize) -> u128 {
140        loop {
141            let config = Some(PrimalityTestConfig::strict());
142            let p = self.gen_prime_exact(bit_size, config);
143            if is_prime(&SmallMint::from(p >> 1), config).probably() {
144                break p;
145            }
146        }
147    }
148}
149
150#[cfg(feature = "num-bigint")]
151impl<R: Rng> RandPrime<BigUint> for R {
152    #[inline]
153    fn gen_prime(&mut self, bit_size: usize, config: Option<PrimalityTestConfig>) -> BigUint {
154        loop {
155            let mut t = self.gen_biguint(bit_size as u64);
156            t.set_bit(0, true); // filter even numbers
157            if is_prime(&t, config).probably() {
158                break t;
159            } else if let Some(p) = next_prime(&t, config) {
160                break p;
161            }
162        }
163    }
164
165    #[inline]
166    fn gen_prime_exact(&mut self, bit_size: usize, config: Option<PrimalityTestConfig>) -> BigUint {
167        loop {
168            let mut t = self.gen_biguint(bit_size as u64);
169            t.set_bit(0, true); // filter even numbers
170            t.set_bit(bit_size as u64 - 1, true);
171            if is_prime(&t, config).probably() {
172                break t;
173            } else if let Some(p) = next_prime(&t, config) {
174                break p;
175            }
176        }
177    }
178
179    #[inline]
180    fn gen_safe_prime(&mut self, bit_size: usize) -> BigUint {
181        let config = Some(PrimalityTestConfig::strict());
182        let p = self.gen_prime(bit_size, config);
183        if is_prime(&(&p >> 1u8), config).probably() {
184            return p;
185        }
186        let p2 = (p << 1u8) + 1u8;
187        if is_prime(&p2, config).probably() {
188            return p2;
189        }
190
191        self.gen_safe_prime(bit_size)
192    }
193
194    #[inline]
195    fn gen_safe_prime_exact(&mut self, bit_size: usize) -> BigUint {
196        let config = Some(PrimalityTestConfig::strict());
197        loop {
198            let p: BigUint = self.gen_prime_exact(bit_size, config);
199            if is_prime(&(&p >> 1u8), config).probably() {
200                return p;
201            }
202        }
203    }
204}
205
206#[cfg(test)]
207mod tests {
208    use super::*;
209    use crate::nt_funcs::is_safe_prime;
210
211    #[test]
212    fn rand_prime() {
213        let mut rng = rand::thread_rng();
214
215        // test random prime generation for each size
216        let p: u8 = rng.gen_prime(8, None);
217        assert!(is_prime64(u64::from(p)));
218        let p: u16 = rng.gen_prime(16, None);
219        assert!(is_prime64(u64::from(p)));
220        let p: u32 = rng.gen_prime(32, None);
221        assert!(is_prime64(u64::from(p)));
222        let p: u64 = rng.gen_prime(64, None);
223        assert!(is_prime64(p));
224        let p: u128 = rng.gen_prime(128, None);
225        assert!(is_prime(&p, None).probably());
226
227        // test random safe prime generation
228        let p: u8 = rng.gen_safe_prime(8);
229        assert!(is_safe_prime(&p).probably());
230        let p: u32 = rng.gen_safe_prime(32);
231        assert!(is_safe_prime(&p).probably());
232        let p: u128 = rng.gen_safe_prime(128);
233        assert!(is_safe_prime(&p).probably());
234
235        #[cfg(feature = "num-bigint")]
236        {
237            let p: BigUint = rng.gen_prime(512, None);
238            assert!(is_prime(&p, None).probably());
239            let p: BigUint = rng.gen_safe_prime(192);
240            assert!(is_safe_prime(&p).probably());
241        }
242
243        // test bit size limit
244        let p: u16 = rng.gen_prime(12, None);
245        assert!(p < (1 << 12));
246        let p: u32 = rng.gen_prime(24, None);
247        assert!(p < (1 << 24));
248    }
249
250    #[test]
251    fn rand_prime_exact() {
252        let mut rng = rand::thread_rng();
253
254        // test exact size prime generation
255        let p: u8 = rng.gen_prime_exact(8, None);
256        assert!(is_prime64(u64::from(p)));
257        assert_eq!(p.leading_zeros(), 0);
258        let p: u32 = rng.gen_prime_exact(32, None);
259        assert!(is_prime64(u64::from(p)));
260        assert_eq!(p.leading_zeros(), 0);
261        let p: u128 = rng.gen_prime_exact(128, None);
262        assert!(is_prime(&p, None).probably());
263        assert_eq!(p.leading_zeros(), 0);
264
265        // test random safe prime generation
266        let p: u8 = rng.gen_safe_prime_exact(8);
267        assert!(is_safe_prime(&p).probably());
268        assert_eq!(p.leading_zeros(), 0);
269        let p: u32 = rng.gen_safe_prime_exact(32);
270        assert!(is_safe_prime(&p).probably());
271        assert_eq!(p.leading_zeros(), 0);
272        let p: u128 = rng.gen_safe_prime_exact(128);
273        assert!(is_safe_prime(&p).probably());
274        assert_eq!(p.leading_zeros(), 0);
275
276        #[cfg(feature = "num-bigint")]
277        {
278            let p: BigUint = rng.gen_prime_exact(192, None);
279            assert!(is_prime(&p, None).probably());
280            assert_eq!(p.bits(), 192);
281            let p: BigUint = rng.gen_safe_prime_exact(192);
282            assert!(is_safe_prime(&p).probably());
283            assert_eq!(p.bits(), 192);
284        }
285    }
286}
num_prime/rand.rs

num_prime/
rand.rs
