num_bigint_dig/
bigrand.rs

1//! Randomization of big integers
2
3use rand::distributions::uniform::{SampleBorrow, SampleUniform, UniformSampler};
4use rand::prelude::*;
5use rand::Rng;
6
7use crate::BigInt;
8use crate::BigUint;
9use crate::Sign::*;
10
11use crate::big_digit::BigDigit;
12use crate::bigint::{into_magnitude, magnitude};
13use crate::integer::Integer;
14#[cfg(feature = "prime")]
15use num_iter::range_step;
16use num_traits::Zero;
17#[cfg(feature = "prime")]
18use num_traits::{FromPrimitive, ToPrimitive};
19
20#[cfg(feature = "prime")]
21use crate::prime::probably_prime;
22
23pub trait RandBigInt {
24    /// Generate a random `BigUint` of the given bit size.
25    fn gen_biguint(&mut self, bit_size: usize) -> BigUint;
26
27    /// Generate a random BigInt of the given bit size.
28    fn gen_bigint(&mut self, bit_size: usize) -> BigInt;
29
30    /// Generate a random `BigUint` less than the given bound. Fails
31    /// when the bound is zero.
32    fn gen_biguint_below(&mut self, bound: &BigUint) -> BigUint;
33
34    /// Generate a random `BigUint` within the given range. The lower
35    /// bound is inclusive; the upper bound is exclusive. Fails when
36    /// the upper bound is not greater than the lower bound.
37    fn gen_biguint_range(&mut self, lbound: &BigUint, ubound: &BigUint) -> BigUint;
38
39    /// Generate a random `BigInt` within the given range. The lower
40    /// bound is inclusive; the upper bound is exclusive. Fails when
41    /// the upper bound is not greater than the lower bound.
42    fn gen_bigint_range(&mut self, lbound: &BigInt, ubound: &BigInt) -> BigInt;
43}
44
45impl<R: Rng + ?Sized> RandBigInt for R {
46    fn gen_biguint(&mut self, bit_size: usize) -> BigUint {
47        use super::big_digit::BITS;
48        let (digits, rem) = bit_size.div_rem(&BITS);
49        let mut data = smallvec![BigDigit::default(); digits + (rem > 0) as usize];
50
51        // `fill` is faster than many `gen::<u32>` calls
52        // Internally this calls `SeedableRng` where implementors are responsible for adjusting endianness for reproducable values.
53        self.fill(data.as_mut_slice());
54
55        if rem > 0 {
56            data[digits] >>= BITS - rem;
57        }
58        BigUint::new_native(data)
59    }
60
61    fn gen_bigint(&mut self, bit_size: usize) -> BigInt {
62        loop {
63            // Generate a random BigUint...
64            let biguint = self.gen_biguint(bit_size);
65            // ...and then randomly assign it a Sign...
66            let sign = if biguint.is_zero() {
67                // ...except that if the BigUint is zero, we need to try
68                // again with probability 0.5. This is because otherwise,
69                // the probability of generating a zero BigInt would be
70                // double that of any other number.
71                if self.gen() {
72                    continue;
73                } else {
74                    NoSign
75                }
76            } else if self.gen() {
77                Plus
78            } else {
79                Minus
80            };
81            return BigInt::from_biguint(sign, biguint);
82        }
83    }
84
85    fn gen_biguint_below(&mut self, bound: &BigUint) -> BigUint {
86        assert!(!bound.is_zero());
87        let bits = bound.bits();
88        loop {
89            let n = self.gen_biguint(bits);
90            if n < *bound {
91                return n;
92            }
93        }
94    }
95
96    fn gen_biguint_range(&mut self, lbound: &BigUint, ubound: &BigUint) -> BigUint {
97        assert!(*lbound < *ubound);
98        if lbound.is_zero() {
99            self.gen_biguint_below(ubound)
100        } else {
101            lbound + self.gen_biguint_below(&(ubound - lbound))
102        }
103    }
104
105    fn gen_bigint_range(&mut self, lbound: &BigInt, ubound: &BigInt) -> BigInt {
106        assert!(*lbound < *ubound);
107        if lbound.is_zero() {
108            BigInt::from(self.gen_biguint_below(magnitude(&ubound)))
109        } else if ubound.is_zero() {
110            lbound + BigInt::from(self.gen_biguint_below(magnitude(&lbound)))
111        } else {
112            let delta = ubound - lbound;
113            lbound + BigInt::from(self.gen_biguint_below(magnitude(&delta)))
114        }
115    }
116}
117
118/// The back-end implementing rand's `UniformSampler` for `BigUint`.
119#[derive(Clone, Debug)]
120pub struct UniformBigUint {
121    base: BigUint,
122    len: BigUint,
123}
124
125impl UniformSampler for UniformBigUint {
126    type X = BigUint;
127
128    #[inline]
129    fn new<B1, B2>(low_b: B1, high_b: B2) -> Self
130    where
131        B1: SampleBorrow<Self::X> + Sized,
132        B2: SampleBorrow<Self::X> + Sized,
133    {
134        let low = low_b.borrow();
135        let high = high_b.borrow();
136
137        assert!(low < high);
138
139        UniformBigUint {
140            len: high - low,
141            base: low.clone(),
142        }
143    }
144
145    #[inline]
146    fn new_inclusive<B1, B2>(low_b: B1, high_b: B2) -> Self
147    where
148        B1: SampleBorrow<Self::X> + Sized,
149        B2: SampleBorrow<Self::X> + Sized,
150    {
151        Self::new(low_b, high_b.borrow() + 1u32)
152    }
153
154    #[inline]
155    fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> Self::X {
156        &self.base + rng.gen_biguint_below(&self.len)
157    }
158
159    #[inline]
160    fn sample_single<R: Rng + ?Sized, B1, B2>(low_b: B1, high_b: B2, rng: &mut R) -> Self::X
161    where
162        B1: SampleBorrow<Self::X> + Sized,
163        B2: SampleBorrow<Self::X> + Sized,
164    {
165        let low = low_b.borrow();
166        let high = high_b.borrow();
167
168        rng.gen_biguint_range(low, high)
169    }
170}
171
172impl SampleUniform for BigUint {
173    type Sampler = UniformBigUint;
174}
175
176/// The back-end implementing rand's `UniformSampler` for `BigInt`.
177#[derive(Clone, Debug)]
178pub struct UniformBigInt {
179    base: BigInt,
180    len: BigUint,
181}
182
183impl UniformSampler for UniformBigInt {
184    type X = BigInt;
185
186    #[inline]
187    fn new<B1, B2>(low_b: B1, high_b: B2) -> Self
188    where
189        B1: SampleBorrow<Self::X> + Sized,
190        B2: SampleBorrow<Self::X> + Sized,
191    {
192        let low = low_b.borrow();
193        let high = high_b.borrow();
194
195        assert!(low < high);
196        UniformBigInt {
197            len: into_magnitude(high - low),
198            base: low.clone(),
199        }
200    }
201
202    #[inline]
203    fn new_inclusive<B1, B2>(low_b: B1, high_b: B2) -> Self
204    where
205        B1: SampleBorrow<Self::X> + Sized,
206        B2: SampleBorrow<Self::X> + Sized,
207    {
208        let low = low_b.borrow();
209        let high = high_b.borrow();
210
211        assert!(low <= high);
212        Self::new(low, high + 1u32)
213    }
214
215    #[inline]
216    fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> Self::X {
217        &self.base + BigInt::from(rng.gen_biguint_below(&self.len))
218    }
219
220    #[inline]
221    fn sample_single<R: Rng + ?Sized, B1, B2>(low_b: B1, high_b: B2, rng: &mut R) -> Self::X
222    where
223        B1: SampleBorrow<Self::X> + Sized,
224        B2: SampleBorrow<Self::X> + Sized,
225    {
226        let low = low_b.borrow();
227        let high = high_b.borrow();
228
229        rng.gen_bigint_range(low, high)
230    }
231}
232
233impl SampleUniform for BigInt {
234    type Sampler = UniformBigInt;
235}
236
237/// A random distribution for `BigUint` and `BigInt` values of a particular bit size.
238#[derive(Clone, Copy, Debug)]
239pub struct RandomBits {
240    bits: usize,
241}
242
243impl RandomBits {
244    #[inline]
245    pub fn new(bits: usize) -> RandomBits {
246        RandomBits { bits }
247    }
248}
249
250impl Distribution<BigUint> for RandomBits {
251    #[inline]
252    fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> BigUint {
253        rng.gen_biguint(self.bits)
254    }
255}
256
257impl Distribution<BigInt> for RandomBits {
258    #[inline]
259    fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> BigInt {
260        rng.gen_bigint(self.bits)
261    }
262}
263
264/// A generic trait for generating random primes.
265///
266/// *Warning*: This is highly dependend on the provided random number generator,
267/// to provide actually random primes.
268///
269/// # Example
270#[cfg_attr(feature = "std", doc = " ```")]
271#[cfg_attr(not(feature = "std"), doc = " ```ignore")]
272/// extern crate rand;
273/// extern crate num_bigint_dig as num_bigint;
274///
275/// use rand::thread_rng;
276/// use num_bigint::RandPrime;
277///
278/// let mut rng = thread_rng();
279/// let p = rng.gen_prime(1024);
280/// assert_eq!(p.bits(), 1024);
281/// ```
282///
283#[cfg(feature = "prime")]
284pub trait RandPrime {
285    /// Generate a random prime number with as many bits as given.
286    fn gen_prime(&mut self, bits: usize) -> BigUint;
287}
288
289/// A list of small, prime numbers that allows us to rapidly
290/// exclude some fraction of composite candidates when searching for a random
291/// prime. This list is truncated at the point where smallPrimesProduct exceeds
292/// a u64. It does not include two because we ensure that the candidates are
293/// odd by construction.
294#[cfg(feature = "prime")]
295const SMALL_PRIMES: [u8; 15] = [3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53];
296
297#[cfg(feature = "prime")]
298lazy_static! {
299    /// The product of the values in SMALL_PRIMES and allows us
300    /// to reduce a candidate prime by this number and then determine whether it's
301    /// coprime to all the elements of SMALL_PRIMES without further BigUint
302    /// operations.
303    static ref SMALL_PRIMES_PRODUCT: BigUint = BigUint::from_u64(16_294_579_238_595_022_365).unwrap();
304}
305
306#[cfg(feature = "prime")]
307impl<R: Rng + ?Sized> RandPrime for R {
308    fn gen_prime(&mut self, bit_size: usize) -> BigUint {
309        if bit_size < 2 {
310            panic!("prime size must be at least 2-bit");
311        }
312
313        let mut b = bit_size % 8;
314        if b == 0 {
315            b = 8;
316        }
317
318        let bytes_len = (bit_size + 7) / 8;
319        let mut bytes = vec![0u8; bytes_len];
320
321        loop {
322            self.fill_bytes(&mut bytes);
323            // Clear bits in the first byte to make sure the candidate has a size <= bits.
324            bytes[0] &= ((1u32 << (b as u32)) - 1) as u8;
325
326            // Don't let the value be too small, i.e, set the most significant two bits.
327            // Setting the top two bits, rather than just the top bit,
328            // means that when two of these values are multiplied together,
329            // the result isn't ever one bit short.
330            if b >= 2 {
331                bytes[0] |= 3u8.wrapping_shl(b as u32 - 2);
332            } else {
333                // Here b==1, because b cannot be zero.
334                bytes[0] |= 1;
335                if bytes_len > 1 {
336                    bytes[1] |= 0x80;
337                }
338            }
339
340            // Make the value odd since an even number this large certainly isn't prime.
341            bytes[bytes_len - 1] |= 1u8;
342
343            let mut p = BigUint::from_bytes_be(&bytes);
344            // must always be a u64, as the SMALL_PRIMES_PRODUCT is a u64
345            let rem = (&p % &*SMALL_PRIMES_PRODUCT).to_u64().unwrap();
346
347            'next: for delta in range_step(0, 1 << 20, 2) {
348                let m = rem + delta;
349
350                for prime in &SMALL_PRIMES {
351                    if m % u64::from(*prime) == 0 && (bit_size > 6 || m != u64::from(*prime)) {
352                        continue 'next;
353                    }
354                }
355
356                if delta > 0 {
357                    p += BigUint::from_u64(delta).unwrap();
358                }
359
360                break;
361            }
362
363            // There is a tiny possibility that, by adding delta, we caused
364            // the number to be one bit too long. Thus we check bit length here.
365            if p.bits() == bit_size && probably_prime(&p, 20) {
366                return p;
367            }
368        }
369    }
370}
num_bigint_dig/bigrand.rs

num_bigint_dig/
bigrand.rs
