Function squfof::square_form_factorization

pub fn square_form_factorization<T: PrimInt + Step>(n: T) -> Option<T> where
    for<'x> &'x T: Rem<&'x T, Output = T>, 

Shanks’s square forms factorization

This function returns Some(divisor) on success. Recommended input is n <= T::MAX / (3 * 5 * 7 * 11).

reference

• Shanks’s square forms factorization
• Jason E. Gower, Samuel S. Wagstaff Jr., Square form factorization, https://doi.org/10.1090/S0025-5718-07-02010-8
• 素因数分解アルゴリズム(特にSQUFOF)のこと

use squfof::square_form_factorization;
let n = 991 * 997;
let f = square_form_factorization(n).unwrap();
assert!(f == 991 || f == 997);