1 //! Randomization of big integers
2 #![cfg(feature = "rand")]
3 #![cfg_attr(docsrs, doc(cfg(feature = "rand")))]
4
5 use rand::distributions::uniform::{SampleBorrow, SampleUniform, UniformSampler};
6 use rand::prelude::*;
7
8 use crate::BigInt;
9 use crate::BigUint;
10 use crate::Sign::*;
11
12 use crate::biguint::biguint_from_vec;
13
14 use num_integer::Integer;
15 use num_traits::{ToPrimitive, Zero};
16
17 /// A trait for sampling random big integers.
18 ///
19 /// The `rand` feature must be enabled to use this. See crate-level documentation for details.
20 pub trait RandBigInt {
21 /// Generate a random [`BigUint`] of the given bit size.
gen_biguint(&mut self, bit_size: u64) -> BigUint22 fn gen_biguint(&mut self, bit_size: u64) -> BigUint;
23
24 /// Generate a random [ BigInt`] of the given bit size.
gen_bigint(&mut self, bit_size: u64) -> BigInt25 fn gen_bigint(&mut self, bit_size: u64) -> BigInt;
26
27 /// Generate a random [`BigUint`] less than the given bound. Fails
28 /// when the bound is zero.
gen_biguint_below(&mut self, bound: &BigUint) -> BigUint29 fn gen_biguint_below(&mut self, bound: &BigUint) -> BigUint;
30
31 /// Generate a random [`BigUint`] within the given range. The lower
32 /// bound is inclusive; the upper bound is exclusive. Fails when
33 /// the upper bound is not greater than the lower bound.
gen_biguint_range(&mut self, lbound: &BigUint, ubound: &BigUint) -> BigUint34 fn gen_biguint_range(&mut self, lbound: &BigUint, ubound: &BigUint) -> BigUint;
35
36 /// Generate a random [`BigInt`] within the given range. The lower
37 /// bound is inclusive; the upper bound is exclusive. Fails when
38 /// the upper bound is not greater than the lower bound.
gen_bigint_range(&mut self, lbound: &BigInt, ubound: &BigInt) -> BigInt39 fn gen_bigint_range(&mut self, lbound: &BigInt, ubound: &BigInt) -> BigInt;
40 }
41
gen_bits<R: Rng + ?Sized>(rng: &mut R, data: &mut [u32], rem: u64)42 fn gen_bits<R: Rng + ?Sized>(rng: &mut R, data: &mut [u32], rem: u64) {
43 // `fill` is faster than many `gen::<u32>` calls
44 rng.fill(data);
45 if rem > 0 {
46 let last = data.len() - 1;
47 data[last] >>= 32 - rem;
48 }
49 }
50
51 impl<R: Rng + ?Sized> RandBigInt for R {
52 cfg_digit!(
53 fn gen_biguint(&mut self, bit_size: u64) -> BigUint {
54 let (digits, rem) = bit_size.div_rem(&32);
55 let len = (digits + (rem > 0) as u64)
56 .to_usize()
57 .expect("capacity overflow");
58 let mut data = vec![0u32; len];
59 gen_bits(self, &mut data, rem);
60 biguint_from_vec(data)
61 }
62
63 fn gen_biguint(&mut self, bit_size: u64) -> BigUint {
64 use core::slice;
65
66 let (digits, rem) = bit_size.div_rem(&32);
67 let len = (digits + (rem > 0) as u64)
68 .to_usize()
69 .expect("capacity overflow");
70 let native_digits = Integer::div_ceil(&bit_size, &64);
71 let native_len = native_digits.to_usize().expect("capacity overflow");
72 let mut data = vec![0u64; native_len];
73 unsafe {
74 // Generate bits in a `&mut [u32]` slice for value stability
75 let ptr = data.as_mut_ptr() as *mut u32;
76 debug_assert!(native_len * 2 >= len);
77 let data = slice::from_raw_parts_mut(ptr, len);
78 gen_bits(self, data, rem);
79 }
80 #[cfg(target_endian = "big")]
81 for digit in &mut data {
82 // swap u32 digits into u64 endianness
83 *digit = (*digit << 32) | (*digit >> 32);
84 }
85 biguint_from_vec(data)
86 }
87 );
88
gen_bigint(&mut self, bit_size: u64) -> BigInt89 fn gen_bigint(&mut self, bit_size: u64) -> BigInt {
90 loop {
91 // Generate a random BigUint...
92 let biguint = self.gen_biguint(bit_size);
93 // ...and then randomly assign it a Sign...
94 let sign = if biguint.is_zero() {
95 // ...except that if the BigUint is zero, we need to try
96 // again with probability 0.5. This is because otherwise,
97 // the probability of generating a zero BigInt would be
98 // double that of any other number.
99 if self.gen() {
100 continue;
101 } else {
102 NoSign
103 }
104 } else if self.gen() {
105 Plus
106 } else {
107 Minus
108 };
109 return BigInt::from_biguint(sign, biguint);
110 }
111 }
112
gen_biguint_below(&mut self, bound: &BigUint) -> BigUint113 fn gen_biguint_below(&mut self, bound: &BigUint) -> BigUint {
114 assert!(!bound.is_zero());
115 let bits = bound.bits();
116 loop {
117 let n = self.gen_biguint(bits);
118 if n < *bound {
119 return n;
120 }
121 }
122 }
123
gen_biguint_range(&mut self, lbound: &BigUint, ubound: &BigUint) -> BigUint124 fn gen_biguint_range(&mut self, lbound: &BigUint, ubound: &BigUint) -> BigUint {
125 assert!(*lbound < *ubound);
126 if lbound.is_zero() {
127 self.gen_biguint_below(ubound)
128 } else {
129 lbound + self.gen_biguint_below(&(ubound - lbound))
130 }
131 }
132
gen_bigint_range(&mut self, lbound: &BigInt, ubound: &BigInt) -> BigInt133 fn gen_bigint_range(&mut self, lbound: &BigInt, ubound: &BigInt) -> BigInt {
134 assert!(*lbound < *ubound);
135 if lbound.is_zero() {
136 BigInt::from(self.gen_biguint_below(ubound.magnitude()))
137 } else if ubound.is_zero() {
138 lbound + BigInt::from(self.gen_biguint_below(lbound.magnitude()))
139 } else {
140 let delta = ubound - lbound;
141 lbound + BigInt::from(self.gen_biguint_below(delta.magnitude()))
142 }
143 }
144 }
145
146 /// The back-end implementing rand's [`UniformSampler`] for [`BigUint`].
147 #[derive(Clone, Debug)]
148 pub struct UniformBigUint {
149 base: BigUint,
150 len: BigUint,
151 }
152
153 impl UniformSampler for UniformBigUint {
154 type X = BigUint;
155
156 #[inline]
new<B1, B2>(low_b: B1, high_b: B2) -> Self where B1: SampleBorrow<Self::X> + Sized, B2: SampleBorrow<Self::X> + Sized,157 fn new<B1, B2>(low_b: B1, high_b: B2) -> Self
158 where
159 B1: SampleBorrow<Self::X> + Sized,
160 B2: SampleBorrow<Self::X> + Sized,
161 {
162 let low = low_b.borrow();
163 let high = high_b.borrow();
164 assert!(low < high);
165 UniformBigUint {
166 len: high - low,
167 base: low.clone(),
168 }
169 }
170
171 #[inline]
new_inclusive<B1, B2>(low_b: B1, high_b: B2) -> Self where B1: SampleBorrow<Self::X> + Sized, B2: SampleBorrow<Self::X> + Sized,172 fn new_inclusive<B1, B2>(low_b: B1, high_b: B2) -> Self
173 where
174 B1: SampleBorrow<Self::X> + Sized,
175 B2: SampleBorrow<Self::X> + Sized,
176 {
177 let low = low_b.borrow();
178 let high = high_b.borrow();
179 assert!(low <= high);
180 Self::new(low, high + 1u32)
181 }
182
183 #[inline]
sample<R: Rng + ?Sized>(&self, rng: &mut R) -> Self::X184 fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> Self::X {
185 &self.base + rng.gen_biguint_below(&self.len)
186 }
187
188 #[inline]
sample_single<R: Rng + ?Sized, B1, B2>(low: B1, high: B2, rng: &mut R) -> Self::X where B1: SampleBorrow<Self::X> + Sized, B2: SampleBorrow<Self::X> + Sized,189 fn sample_single<R: Rng + ?Sized, B1, B2>(low: B1, high: B2, rng: &mut R) -> Self::X
190 where
191 B1: SampleBorrow<Self::X> + Sized,
192 B2: SampleBorrow<Self::X> + Sized,
193 {
194 rng.gen_biguint_range(low.borrow(), high.borrow())
195 }
196 }
197
198 impl SampleUniform for BigUint {
199 type Sampler = UniformBigUint;
200 }
201
202 /// The back-end implementing rand's [`UniformSampler`] for [`BigInt`].
203 #[derive(Clone, Debug)]
204 pub struct UniformBigInt {
205 base: BigInt,
206 len: BigUint,
207 }
208
209 impl UniformSampler for UniformBigInt {
210 type X = BigInt;
211
212 #[inline]
new<B1, B2>(low_b: B1, high_b: B2) -> Self where B1: SampleBorrow<Self::X> + Sized, B2: SampleBorrow<Self::X> + Sized,213 fn new<B1, B2>(low_b: B1, high_b: B2) -> Self
214 where
215 B1: SampleBorrow<Self::X> + Sized,
216 B2: SampleBorrow<Self::X> + Sized,
217 {
218 let low = low_b.borrow();
219 let high = high_b.borrow();
220 assert!(low < high);
221 UniformBigInt {
222 len: (high - low).into_parts().1,
223 base: low.clone(),
224 }
225 }
226
227 #[inline]
new_inclusive<B1, B2>(low_b: B1, high_b: B2) -> Self where B1: SampleBorrow<Self::X> + Sized, B2: SampleBorrow<Self::X> + Sized,228 fn new_inclusive<B1, B2>(low_b: B1, high_b: B2) -> Self
229 where
230 B1: SampleBorrow<Self::X> + Sized,
231 B2: SampleBorrow<Self::X> + Sized,
232 {
233 let low = low_b.borrow();
234 let high = high_b.borrow();
235 assert!(low <= high);
236 Self::new(low, high + 1u32)
237 }
238
239 #[inline]
sample<R: Rng + ?Sized>(&self, rng: &mut R) -> Self::X240 fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> Self::X {
241 &self.base + BigInt::from(rng.gen_biguint_below(&self.len))
242 }
243
244 #[inline]
sample_single<R: Rng + ?Sized, B1, B2>(low: B1, high: B2, rng: &mut R) -> Self::X where B1: SampleBorrow<Self::X> + Sized, B2: SampleBorrow<Self::X> + Sized,245 fn sample_single<R: Rng + ?Sized, B1, B2>(low: B1, high: B2, rng: &mut R) -> Self::X
246 where
247 B1: SampleBorrow<Self::X> + Sized,
248 B2: SampleBorrow<Self::X> + Sized,
249 {
250 rng.gen_bigint_range(low.borrow(), high.borrow())
251 }
252 }
253
254 impl SampleUniform for BigInt {
255 type Sampler = UniformBigInt;
256 }
257
258 /// A random distribution for [`BigUint`] and [`BigInt`] values of a particular bit size.
259 ///
260 /// The `rand` feature must be enabled to use this. See crate-level documentation for details.
261 #[derive(Clone, Copy, Debug)]
262 pub struct RandomBits {
263 bits: u64,
264 }
265
266 impl RandomBits {
267 #[inline]
new(bits: u64) -> RandomBits268 pub fn new(bits: u64) -> RandomBits {
269 RandomBits { bits }
270 }
271 }
272
273 impl Distribution<BigUint> for RandomBits {
274 #[inline]
sample<R: Rng + ?Sized>(&self, rng: &mut R) -> BigUint275 fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> BigUint {
276 rng.gen_biguint(self.bits)
277 }
278 }
279
280 impl Distribution<BigInt> for RandomBits {
281 #[inline]
sample<R: Rng + ?Sized>(&self, rng: &mut R) -> BigInt282 fn sample<R: Rng + ?Sized>(&self, rng: &mut R) -> BigInt {
283 rng.gen_bigint(self.bits)
284 }
285 }
286