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

Functions

one_line64

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

one_line128

William Hart’s one line factorization algorithm for 128 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). It will assume that target is not a perfect square and the multiplier is square-free.

trial_division

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