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.