Expand description
Primality testing and prime generation for cryptography, over the
integers of tc_bigint and the modular arithmetic of tc_modular,
with the random integers they draw on.
Primality tests and generates probable primes as Bouncy Castle’s
Primes does: trial division by the primes below 212, then rounds of
Miller-Rabin, or the enhanced test of FIPS 186-4 C.3.2, which tells a
composite apart and may find a factor of it. ShaweTaylor, behind the
shawe-taylor feature, generates provable primes by the routine of
FIPS 186-4 C.6 from a digest of tc_digest and a seed. Both are
implemented for FixedBigUint<N> and, with alloc, for PaddedBigUint
and BigUint. The random values come from a rand_core generator that
the caller gives.
use tc_bigint::{BitOps, FixedBigUint, Word};
use tc_prime::Primality;
type U256 = FixedBigUint<{ 256 / Word::BITS as usize }>;
// any generator of rand_core; a seeded one keeps the example repeatable
let mut rng = Xorshift(0x2545_f491_4f6c_dd1d);
let p = U256::from(i128::MAX as u128); // 2^127 - 1, a prime
assert!(p.is_probable_prime(40, &mut rng));
assert!(!(&p * &p).is_probable_prime(40, &mut rng));
let q = U256::random_probable_prime(&mut rng, 256, 40);
assert_eq!(q.bits(), 256);§Timing
Primality testing and generation are variable time over every integer type, as Bouncy Castle’s are: only for public values, or for candidates whose timing a caller accepts showing, as key generation does. Every method says which it is.
Structs§
- StOutput
- A provable prime, with the seed and the prime generation counter the routine ends at, which FIPS 186-4 keeps for validation.
Enums§
- MrOutput
- What the enhanced Miller-Rabin test found, as Bouncy Castle’s
Primes.MROutputreports it. - StError
- Why the Shawe-Taylor routine gave no prime.
Traits§
- Primality
- Primality as Bouncy Castle tests it: trial division, Miller-Rabin, and random probable primes. Each implementation states whether it is constant time.
- Shawe
Taylor - Provable primes by the Shawe-Taylor routine of FIPS 186-4 C.6, as Bouncy Castle runs it. Each implementation states whether it is constant time.