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 a method for recognising such one-sided identities is required. In general, one finds them by performing operations that move elements around and leave the identities in the reduced groups unchanged. Once the algorithm finds a one-sided identity all future terms will also be one-sided identities, so checking periodically suffices.
Computation proceeds by picking an arbitrary element x of the group modulo N and computing 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, as the element might be 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, the check is made for a one-sided identity.
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 is actually a quadratic extension of N without knowing the factorisation. This requires knowing whether t is a quadratic residue 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 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; Hasse's theorem states that the number of points on an elliptic curve modulo p is always within of p.
All three of the above algebraic groups are used by the GMP-ECM 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 binary exponentiation 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.