Function squfof::square_form_factorization [−][src]
pub fn square_form_factorization<T: PrimInt + Step>(n: T) -> Option<T> where
for<'x> &'x T: Rem<&'x T, Output = T>,
Expand description
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);