Algebraic-group factorisation algorithm

Algebraic-group factorisation algorithms are algorithms for factoring an integer N by working in an algebraic group defined 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₂, ... By the Chinese Remainder Theorem, arithmetic modulo N corresponds to arithmetic in all the reduced groups simultaneously.

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'. In general, you find them by performing operations which move elements around and leave the identities in the reduced groups unchanged; once you hit a one-sided identity all future terms will also be one-sided identities, so you can check periodically.

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 at least one but not all of the reduced groups is a divisor of A, this yields a factorisation. It need not be a prime factorisation, if you have found an element which is an identity in more than one of the reduced groups.

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, or every few multiplications, 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 divisors 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 modulo N, 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.