Struct num_prime::PrimalityTestConfig

#[non_exhaustive]
pub struct PrimalityTestConfig {
    pub sprp_trials: usize,
    pub sprp_random_trials: usize,
    pub slprp_test: bool,
    pub eslprp_test: bool,
}

Represents a configuration for a primality test

Fields (Non-exhaustive)

Non-exhaustive structs could have additional fields added in future. Therefore, non-exhaustive structs cannot be constructed in external crates using the traditional Struct { .. } syntax; cannot be matched against without a wildcard ..; and struct update syntax will not work.

sprp_trials: usize

Number of strong probable prime test, starting from base 2

sprp_random_trials: usize

Number of strong probable prime test with random bases

slprp_test: bool

Whether perform strong lucas probable prime test (with automatically selected parameters)

eslprp_test: bool

Whether perform extra strong lucas probable prime test (with automatically selected parameters)

Implementations

impl PrimalityTestConfig

pub fn strict() -> Self

Create a configuration with a very strong primality check. It’s based on the strongest deterministic primality testing and some SPRP tests with random bases.

Examples found in repository

src/traits.rs (line 177)

    pub fn strict() -> Self {
        let mut config = Self::default();
        config.primality_config = PrimalityTestConfig::strict();
        config
    }

src/nt_funcs.rs (line 804)

pub fn is_safe_prime<T: PrimalityBase>(target: &T) -> Primality
where
    for<'r> &'r T: PrimalityRefBase<T>,
{
    let buf = NaiveBuffer::new();
    let config = Some(PrimalityTestConfig::strict());

    // test (n-1)/2 first since its smaller
    let sophie_p = buf.is_prime(&(target >> 1), config);
    if matches!(sophie_p, Primality::No) {
        return sophie_p;
    }

    // and then test target itself
    let target_p = buf.is_prime(target, config);
    target_p & sophie_p
}

src/rand.rs (line 129)

    fn gen_safe_prime(&mut self, bit_size: usize) -> u128 {
        loop {
            let config = Some(PrimalityTestConfig::strict());
            let p = self.gen_prime(bit_size, config);
            if is_prime(&SmallMint::from(p >> 1), config).probably() {
                break p;
            }
            if let Some(p2) = p.checked_mul(2).and_then(|v| v.checked_add(1)) {
                if is_prime(&p2, config).probably() {
                    break p2;
                }
            }
        }
    }

    #[inline]
    fn gen_safe_prime_exact(&mut self, bit_size: usize) -> u128 {
        loop {
            let config = Some(PrimalityTestConfig::strict());
            let p = self.gen_prime_exact(bit_size, config);
            if is_prime(&SmallMint::from(p >> 1), config).probably() {
                break p;
            }
            if let Some(p2) = p.checked_mul(2).and_then(|v| v.checked_add(1)) {
                if is_prime(&p2, config).probably() {
                    break p2;
                }
            }
        }
    }
}

#[cfg(feature = "num-bigint")]
impl<R: Rng> RandPrime<BigUint> for R {
    #[inline]
    fn gen_prime(&mut self, bit_size: usize, config: Option<PrimalityTestConfig>) -> BigUint {
        loop {
            let mut t = self.gen_biguint(bit_size as u64);
            t.set_bit(0, true); // filter even numbers
            if is_prime(&t, config).probably() {
                break t;
            } else if let Some(p) = next_prime(&t, config) {
                break p;
            }
        }
    }

    #[inline]
    fn gen_prime_exact(&mut self, bit_size: usize, config: Option<PrimalityTestConfig>) -> BigUint {
        loop {
            let mut t = self.gen_biguint(bit_size as u64);
            t.set_bit(0, true); // filter even numbers
            t.set_bit(bit_size as u64 - 1, true);
            if is_prime(&t, config).probably() {
                break t;
            } else if let Some(p) = next_prime(&t, config) {
                break p;
            }
        }
    }

    #[inline]
    fn gen_safe_prime(&mut self, bit_size: usize) -> BigUint {
        let config = Some(PrimalityTestConfig::strict());
        let p = self.gen_prime(bit_size, config);
        if is_prime(&(&p >> 1u8), config).probably() {
            return p;
        }
        let p2 = (p << 1u8) + 1u8;
        if is_prime(&p2, config).probably() {
            return p2;
        }

        self.gen_safe_prime(bit_size)
    }

    #[inline]
    fn gen_safe_prime_exact(&mut self, bit_size: usize) -> BigUint {
        let config = Some(PrimalityTestConfig::strict());
        let p = self.gen_prime_exact(bit_size, config);
        if is_prime(&(&p >> 1u8), config).probably() {
            return p;
        }
        let p2 = (p << 1u8) + 1u8;
        if is_prime(&p2, config).probably() {
            return p2;
        }

        self.gen_safe_prime(bit_size)
    }

pub fn bpsw() -> Self

Create a configuration for Baillie-PSW test (base 2 SPRP test + SLPRP test)

Examples found in repository

src/traits.rs (line 116)

    pub fn strict() -> Self {
        let mut config = Self::bpsw();
        config.sprp_random_trials = 1;
        config
    }

src/nt_funcs.rs (line 395)

pub(crate) fn factorize128_advanced(cofactors: &[(u128, usize)]) -> Vec<(u128, usize)> {
    let (mut todo128, mut todo64) = (Vec::new(), Vec::new()); // cofactors to be processed
    let mut factored: Vec<(u128, usize)> = Vec::new(); // prime factor, exponent
    for &(co, e) in cofactors.iter() {
        if let Ok(co64) = u64::try_from(co) {
            todo64.push((co64, e));
        } else {
            todo128.push((co, e));
        };
    }

    while let Some((target, exp)) = todo128.pop() {
        if is_prime(&SmallMint::from(target), Some(PrimalityTestConfig::bpsw())).probably() {
            factored.push((target, exp));
            continue;
        }

        // check perfect powers before other methods
        // it suffices to check 2, 3, 5, 7 power if big-table is enabled, since tenth power of
        // the smallest prime that haven't been checked is 8167^10 > 2^128
        if let Some(d) = target.sqrt_exact() {
            if let Ok(d64) = u64::try_from(d) {
                todo64.push((d64, exp * 2));
            } else {
                todo128.push((d, exp * 2));
            }
            continue;
        }
        if let Some(d) = target.cbrt_exact() {
            if let Ok(d64) = u64::try_from(d) {
                todo64.push((d64, exp * 3));
            } else {
                todo128.push((d, exp * 3));
            }
            continue;
        }
        // TODO: check 5-th, 7-th power

        // try to find a divisor
        let mut i = 0usize;
        let mut max_iter_ratio = 1;

        let divisor = loop {
            // try various factorization method iteratively, sort by time per iteration
            const NMETHODS: usize = 3;
            match i % NMETHODS {
                0 => {
                    // Pollard's rho
                    let start = MontgomeryInt::new(random::<u128>(), &target);
                    let offset = start.convert(random::<u128>());
                    let max_iter = max_iter_ratio << (target.bits() / 6); // unoptimized heuristic
                    if let (Some(p), _) = pollard_rho(
                        &SmallMint::from(target),
                        start.into(),
                        offset.into(),
                        max_iter,
                    ) {
                        break p.value();
                    }
                }
                1 => {
                    // Hart's one-line
                    let mul_target = target.checked_mul(480).unwrap_or(target);
                    let max_iter = max_iter_ratio << (mul_target.bits() / 6); // unoptimized heuristic
                    if let (Some(p), _) = one_line(&target, mul_target, max_iter) {
                        break p;
                    }
                }
                2 => {
                    // Shanks's squfof, try all mutipliers
                    let mut d = None;
                    for &k in SQUFOF_MULTIPLIERS.iter() {
                        if let Some(mul_target) = target.checked_mul(k as u128) {
                            let max_iter = max_iter_ratio * 2 * mul_target.sqrt().sqrt() as usize;
                            if let (Some(p), _) = squfof(&target, mul_target, max_iter) {
                                d = Some(p);
                                break;
                            }
                        }
                    }
                    if let Some(p) = d {
                        break p;
                    }
                }
                _ => unreachable!(),
            }
            i += 1;

            // increase max iterations after trying all methods
            if i % NMETHODS == 0 {
                max_iter_ratio *= 2;
            }
        };

        if let Ok(d64) = u64::try_from(divisor) {
            todo64.push((d64, exp));
        } else {
            todo128.push((divisor, exp));
        }
        let co = target / divisor;
        if let Ok(d64) = u64::try_from(co) {
            todo64.push((d64, exp));
        } else {
            todo128.push((co, exp));
        }
    }

    // forward 64 bit cofactors
    factored.extend(
        factorize64_advanced(&todo64)
            .into_iter()
            .map(|(p, exp)| (p as u128, exp)),
    );
    factored
}

Trait Implementations

impl Clone for PrimalityTestConfig

fn clone(&self) -> PrimalityTestConfig

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for PrimalityTestConfig

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl Default for PrimalityTestConfig

fn default() -> Self

Create a defalt primality testing configuration. This config will eliminate most composites with little computation

impl Copy for PrimalityTestConfig