Algebraic-group factorisation algorithm

<h2 id="the-two-step-procedure">The two-step procedure</h2>
It is often possible to multiply a group element by several small integers more quickly than by their product, generally by difference-based methods; one calculates differences between consecutive primes and adds consecutively by the 
 
 
 
 
 d
 
 i
 
 
 r
 
 
 {\displaystyle d_{i}r}
 
. This means that a two-step procedure becomes sensible, first computing Ax by multiplying x by all the primes below a limit B1, and then examining p Ax for all the primes between B1 and a larger limit B2.

<h2 id="methods-corresponding-to-particular-algebraic-groups">Methods corresponding to particular algebraic groups</h2>
If the algebraic group is the <a href="/facts/Multiplicative_group/G209dICf">multiplicative group</a> mod N, the one-sided identities are recognised by computing <a href="/facts/Greatest_common_divisor/kNFvBuKl">greatest common divisors</a> with N, and the result is the <a href="/facts/Pollard%2527s_p-1_algorithm/dITySRp5">p − 1 method</a>.
If the algebraic group is the multiplicative group of a quadratic extension of N, the result is the <a href="/facts/Williams%2527_p_%252B_1_algorithm/qPlGLfS7">p + 1 method</a>; the calculation involves pairs of numbers modulo N. It is not possible to tell whether 
 
 
 
 
 Z
 
 
 /
 
 N
 
 Z
 
 [
 
 
 t
 
 
 ]
 
 
 {\displaystyle \mathbb {Z} /N\mathbb {Z} [{\sqrt {t}}]}
 
 is actually a quadratic extension of 
 
 
 
 
 Z
 
 
 /
 
 N
 
 Z
 
 
 
 {\displaystyle \mathbb {Z} /N\mathbb {Z} }
 
 without knowing the factorisation of N. This requires knowing whether t is a <a href="/facts/Quadratic_residue/rHD2uQdQ">quadratic residue</a> modulo N, and there are no known methods for doing this without knowledge of the factorisation. However, provided N does not have a very large number of factors, in which case another method should be used first, picking random t (or rather picking A with t = A2 − 4) will accidentally hit a quadratic non-residue fairly quickly. If t is a quadratic residue, the p+1 method degenerates to a slower form of the p − 1 method.
If the algebraic group is an <a href="/facts/Elliptic_curve/60jvaHSA">elliptic curve</a>, the one-sided identities can be recognised by failure of <a href="/facts/Inverse_function/Tg5nnXlu">inversion</a> in the elliptic-curve point addition procedure, and the result is the <a href="/facts/Elliptic_curve_method/PwdIdtQW">elliptic curve method</a>; <a href="/facts/Hasse%2527s_theorem_on_elliptic_curves/HDvvYpjX">Hasse's theorem</a> states that the number of points on an elliptic curve modulo p is always within 
 
 
 
 2
 
 
 p
 
 
 
 
 {\displaystyle 2{\sqrt {p}}}
 
 of p.
All three of the above algebraic groups are used by the <a href="https://gitlab.inria.fr/zimmerma/ecm">GMP-ECM</a> package, which includes efficient implementations of the two-stage procedure, and an implementation of the PRAC group-exponentiation algorithm which is rather more efficient than the standard <a href="/facts/Binary_exponentiation/HP8H37AA">binary exponentiation</a> approach.
The use of other algebraic groups—higher-order extensions of N or groups corresponding to algebraic curves of higher genus—is occasionally proposed, but almost always impractical. These methods end up with smoothness constraints on numbers of the order of pd for some d > 1, which are much less likely to be smooth than numbers of the order of p.

Algebraic-group factorisation algorithm open-in-new

Algebraic-group factorisation algorithm