Skip to main content

Crate tc_prime

Crate tc_prime 

Source
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.MROutput reports 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.
ShaweTaylor
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.