In general, one finds them by performing operations that move elements around and leave the identities in the reduced groups unchanged.
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 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
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 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.