tc_prime 0.1.0

Primality testing and prime generation for cryptography over the integers of tc_bigint: trial division, Miller-Rabin and Shawe-Taylor provable primes.
Documentation

tc_prime

crates.io docs.rs CI license rustc

Primality testing and prime generation for cryptography over the integers of tc_bigint, after Bouncy Castle's Primes: trial division, Miller-Rabin, the enhanced test of FIPS 186-4, and Shawe-Taylor provable primes. no_std, no unsafe, Rust 1.85 or later.

Types

  • MrOutput<T> — what the enhanced Miller-Rabin test found: probably prime, or composite with or without a factor.
  • StOutput<T> (shawe-taylor) — a provable prime, with the seed and counter the routine ends at.
  • StError (shawe-taylor) — why the Shawe-Taylor routine gave no prime.

Traits

  • Primality — trial division, Miller-Rabin, the enhanced test and random probable primes, on FixedBigUint<N>, PaddedBigUint and BigUint.
  • ShaweTaylor (shawe-taylor) — provable primes by FIPS 186-4 C.6 from a tc_digest digest and a seed.

Features

  • alloc (off by default) — the traits on PaddedBigUint and BigUint.
  • shawe-taylor (off by default) — ShaweTaylor, which adds tc_digest and turns on alloc.

Usage

use tc_bigint::{FixedBigUint, Word};
use tc_prime::Primality;

type U256 = FixedBigUint<{ 256 / Word::BITS as usize }>;

let p = U256::from(i128::MAX as u128); // 2^127 - 1, a prime
assert!(!p.has_small_factor());
assert!(p.is_probable_prime_to_base(&U256::from(2u8)));

Security

Every test and generator is variable time, as Bouncy Castle's are: only for public values, or for candidates whose timing a caller accepts showing, as key generation does. The random values come from the rand_core generator the caller gives, which has to be cryptographically secure for key generation. This is a learning port with no independent security audit.

License

Licensed under either the MIT license or the Apache License, Version 2.0, at your option.