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 p1, p2, ...
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
== Specific methods
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
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.