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        if bit_size > (u128::BITS as usize) {
87            panic!("The given bit size limit exceeded the capacity of the integer type!")
88        }
89
90        loop {
91            let t: u128 = self.gen();
92            let t = (t >> (u128::BITS - bit_size as u32)) | 1; // filter even numbers
93            if is_prime(&SmallMint::from(t), config).probably() {
94                break t;
95            } else if let Some(p) = next_prime(&t, None) {
96                // deterministic primality test will be used for integers under u64
97                break p;
98            }
99        }
100    }
101
102    #[inline]
103    fn gen_prime_exact(&mut self, bit_size: usize, config: Option<PrimalityTestConfig>) -> u128 {
104        if bit_size > (u128::BITS as usize) {
105            panic!("The given bit size limit exceeded the capacity of the integer type!")
106        }
107
108        loop {
109            let t: u128 = self.gen();
110            let t = (t >> (u128::BITS - bit_size as u32)) | 1 | (1 << (bit_size - 1));
111            if is_prime(&SmallMint::from(t), config).probably() {
112                break t;
113            } else if let Some(p) = next_prime(&t, None) {
114                // deterministic primality test will be used for integers under u64
115                break p;
116            }
117        }
118    }
119
120    #[inline]
121    fn gen_safe_prime(&mut self, bit_size: usize) -> u128 {
122        loop {
123            let config = Some(PrimalityTestConfig::strict());
124            let p = self.gen_prime(bit_size, config);
125            if is_prime(&SmallMint::from(p >> 1), config).probably() {
126                break p;
127            }
128            if let Some(p2) = p.checked_mul(2).and_then(|v| v.checked_add(1)) {
129                if is_prime(&p2, config).probably() {
130                    break p2;
131                }
132            }
133        }
134    }
135
136    #[inline]
137    fn gen_safe_prime_exact(&mut self, bit_size: usize) -> u128 {
138        loop {
139            let config = Some(PrimalityTestConfig::strict());
140            let p = self.gen_prime_exact(bit_size, config);
141            if is_prime(&SmallMint::from(p >> 1), config).probably() {
142                break p;
143            }
144        }
145    }
146}
147
148#[cfg(feature = "num-bigint")]
149impl<R: Rng> RandPrime<BigUint> for R {
150    #[inline]
151    fn gen_prime(&mut self, bit_size: usize, config: Option<PrimalityTestConfig>) -> BigUint {
152        loop {
153            let mut t = self.gen_biguint(bit_size as u64);
154            t.set_bit(0, true); // filter even numbers
155            if is_prime(&t, config).probably() {
156                break t;
157            } else if let Some(p) = next_prime(&t, config) {
158                break p;
159            }
160        }
161    }
162
163    #[inline]
164    fn gen_prime_exact(&mut self, bit_size: usize, config: Option<PrimalityTestConfig>) -> BigUint {
165        loop {
166            let mut t = self.gen_biguint(bit_size as u64);
167            t.set_bit(0, true); // filter even numbers
168            t.set_bit(bit_size as u64 - 1, true);
169            if is_prime(&t, config).probably() {
170                break t;
171            } else if let Some(p) = next_prime(&t, config) {
172                break p;
173            }
174        }
175    }
176
177    #[inline]
178    fn gen_safe_prime(&mut self, bit_size: usize) -> BigUint {
179        let config = Some(PrimalityTestConfig::strict());
180        let p = self.gen_prime(bit_size, config);
181        if is_prime(&(&p >> 1u8), config).probably() {
182            return p;
183        }
184        let p2 = (p << 1u8) + 1u8;
185        if is_prime(&p2, config).probably() {
186            return p2;
187        }
188
189        self.gen_safe_prime(bit_size)
190    }
191
192    #[inline]
193    fn gen_safe_prime_exact(&mut self, bit_size: usize) -> BigUint {
194        let config = Some(PrimalityTestConfig::strict());
195        loop {
196            let p: BigUint = self.gen_prime_exact(bit_size, config);
197            if is_prime(&(&p >> 1u8), config).probably() {
198                return p;
199            }
200        }
201    }
202}
203
204#[cfg(test)]
205mod tests {
206    use super::*;
207    use crate::nt_funcs::is_safe_prime;
208
209    #[test]
210    fn rand_prime() {
211        let mut rng = rand::thread_rng();
212
213        // test random prime generation for each size
214        let p: u8 = rng.gen_prime(8, None);
215        assert!(is_prime64(p as u64));
216        let p: u16 = rng.gen_prime(16, None);
217        assert!(is_prime64(p as u64));
218        let p: u32 = rng.gen_prime(32, None);
219        assert!(is_prime64(p as u64));
220        let p: u64 = rng.gen_prime(64, None);
221        assert!(is_prime64(p));
222        let p: u128 = rng.gen_prime(128, None);
223        assert!(is_prime(&p, None).probably());
224
225        // test random safe prime generation
226        let p: u8 = rng.gen_safe_prime(8);
227        assert!(is_safe_prime(&p).probably());
228        let p: u32 = rng.gen_safe_prime(32);
229        assert!(is_safe_prime(&p).probably());
230        let p: u128 = rng.gen_safe_prime(128);
231        assert!(is_safe_prime(&p).probably());
232
233        #[cfg(feature = "num-bigint")]
234        {
235            let p: BigUint = rng.gen_prime(512, None);
236            assert!(is_prime(&p, None).probably());
237            let p: BigUint = rng.gen_safe_prime(192);
238            assert!(is_safe_prime(&p).probably());
239        }
240
241        // test bit size limit
242        let p: u16 = rng.gen_prime(12, None);
243        assert!(p < (1 << 12));
244        let p: u32 = rng.gen_prime(24, None);
245        assert!(p < (1 << 24));
246    }
247
248    #[test]
249    fn rand_prime_exact() {
250        let mut rng = rand::thread_rng();
251
252        // test exact size prime generation
253        let p: u8 = rng.gen_prime_exact(8, None);
254        assert!(is_prime64(p as u64));
255        assert_eq!(p.leading_zeros(), 0);
256        let p: u32 = rng.gen_prime_exact(32, None);
257        assert!(is_prime64(p as u64));
258        assert_eq!(p.leading_zeros(), 0);
259        let p: u128 = rng.gen_prime_exact(128, None);
260        assert!(is_prime(&p, None).probably());
261        assert_eq!(p.leading_zeros(), 0);
262        
263        // test random safe prime generation
264        let p: u8 = rng.gen_safe_prime_exact(8);
265        assert!(is_safe_prime(&p).probably());
266        assert_eq!(p.leading_zeros(), 0);
267        let p: u32 = rng.gen_safe_prime_exact(32);
268        assert!(is_safe_prime(&p).probably());
269        assert_eq!(p.leading_zeros(), 0);
270        let p: u128 = rng.gen_safe_prime_exact(128);
271        assert!(is_safe_prime(&p).probably());
272        assert_eq!(p.leading_zeros(), 0);
273
274        #[cfg(feature = "num-bigint")]
275        {
276            let p: BigUint = rng.gen_prime_exact(192, None);
277            assert!(is_prime(&p, None).probably());
278            assert_eq!(p.bits(), 192);
279            let p: BigUint = rng.gen_safe_prime_exact(192);
280            assert!(is_safe_prime(&p).probably());
281            assert_eq!(p.bits(), 192);
282        }
283    }
284}
num_prime/rand.rs

num_prime/
rand.rs
