class_groups/
primes.rs

1use core::num::NonZero;
2
3use rand::CryptoRng;
4
5use crypto_bigint::{Unsigned, UnsignedWithMontyForm, RandomMod};
6
7/// Get the candidates for the next prime greater than or equal to the seed.
8///
9/// This function runs in variable time.
10///
11/// This returns an iterator of candidates.
12fn next_prime_candidates<U: Unsigned>(seed: U) -> impl Iterator<Item = U> {
13  let max_bit_length = NonZero::new(seed.bits_precision()).unwrap();
14  match crypto_primes::hazmat::SmallFactorsSieve::new(seed, max_bit_length, false) {
15    Ok(iter) => iter,
16    // We explicitly set `max_bit_length = bits_precision`
17    Err(crypto_primes::Error::BitLengthTooLarge { .. }) => {
18      unreachable!("`max_bit_length = bits_precision`")
19    }
20    // Inapplicable to this context
21    Err(crypto_primes::Error::BitLengthTooSmall { .. }) => unreachable!(),
22  }
23}
24
25#[derive(Debug)]
26pub(super) enum Error {
27  NoMillerRabin,
28  Capacity,
29}
30
31/// Get the next prime greater than or equal to the seed.
32///
33/// This function runs in variable time.
34///
35/// The returned value is composite with probability `2^{-bits_of_security}`, per FIPS-186.5, for
36/// parameterization of the Miller-Rabin test, unconditionally followed by a Lucas test.
37pub(super) fn next_prime<U: UnsignedWithMontyForm + RandomMod>(
38  mut rng: impl CryptoRng,
39  seed: U,
40  bits_of_security: u32,
41) -> Result<U, Error> {
42  let candidates = next_prime_candidates(seed);
43  for candidate in candidates {
44    let options =
45      crypto_primes::fips::FipsOptions::with_error_bound(candidate.bits(), bits_of_security)
46        .ok_or(Error::NoMillerRabin)?
47        .with_lucas_test();
48    if crypto_primes::fips::is_prime(&mut rng, crypto_primes::Flavor::Any, &candidate, options) {
49      return Ok(candidate);
50    }
51  }
52  Err(Error::Capacity)
53}
class_groups/primes.rs

class_groups/
primes.rs
