Algebraic-group factorisation algorithm

Algebraic-group factorisation algorithms are algorithms for factoring an integer N by working in an algebraic group modulo N whose group structure is the direct sum of the 'reduced groups' obtained by performing the equations defining the group arithmetic modulo the unknown prime factors p₁, p₂, ...

The aim is to find an element which is not the identity of the group modulo N, but is the identity modulo one of the factors, so you need a method for recognising such elements; I will call these 'one-sided identities'.

You then pick an arbitrary element x of the group modulo N, and compute a large and smooth multiple Ax of it; if the order of any of the reduced groups is a divisor of A, this yields a factorisation.

Generally, A is taken as a product of the primes below some limit K, and Ax is computed by successive multiplication of x by these primes; after each multiplication you can check whether you have hit a one-sided identity.

The two-step procedure

It is often possible to multiply a group element by several small integers independently more quickly than you can multiply by their product, which means that a two-step procedure becomes sensible; you compute Ax by multiplying x by all the primes below a limit B1, and then examine p Ax for all the primes between B1 and a larger limit B2.

Methods corresponding to particular algebraic groups

If the algebraic group is the multiplicative group mod N, the one-sided identities are recognised by computing greatest common denominators with N, and the result is the p-1 method.

If the algebraic group is the multiplicative group of a quadratic extension of N, the result is the p+1 method; the calculation involves pairs of numbers modulo N. It is not possible to tell whether $\mathbb {Z} /n\mathbb {Z} [{\sqrt {t}}]$ is actually a quadratic extension of N without knowing the factorisation - you have to know whether t is a quadratic residue, and there are no known methods for doing this without knowledge of the factorisation - but provided N does not have a very large number of factors, in which case you would have used another method first, picking random t will accidentally hit a quadratic residue fairly quickly. If t is not a quadratic residue, the p+1 method degenerates to a slower form of the p-1 method.

If the algebraic group is an elliptic curve, the one-sided identities can be recognised by failure of inversion in the elliptic-curve point addition procedure, and the result is the elliptic curve method.