Module num_prime::factor

Implementations for various factorization algorithms.

Note general prime number field sieve is not planned to be implemented, since it’s too complex

See https://web.archive.org/web/20110331180514/https://diamond.boisestate.edu/~liljanab/BOISECRYPTFall09/Jacobsen.pdf for a detailed comparison between different factorization algorithms

Constants

SQUFOF_MULTIPLIERS

Good squfof multipliers sorted by efficiency descendingly, from Dana Jacobsen.

Functions

one_line

William Hart’s one line factorization algorithm for 64 bit integers.

pollard_rho

Find factors using Pollard’s rho algorithm with Brent’s loop detection algorithm

squfof

This function implements Shanks’s square forms factorization (SQUFOF).

trial_division

Find factors by trial division, returns a tuple of the found factors and the residual.