[−][src]Function accumulator::hash::primality::is_prob_prime

pub fn is_prob_prime(n: &U256) -> bool

Implements the Baillie-PSW probabilistic primality test, which is known to be deterministic over all integers up to 64 bits.

Outperforms naked Miller-Rabin (i.e. iterated Fermat tests of random base) at wide n since Fermat and Lucas pseudoprimes have been shown to be anticorrelated. Steps of BPSW are as follows:

  1. Accept small primes and reject multiples of them.
  2. Do a single iteration of Miller-Rabin (in particular, a base-2 Fermat test).
  3. Do a strong probabilistic Lucas test (squares filtered during test initialization).