actually a quadratic extension of without knowing the factorisation of N. 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 non-residue fairly quickly. If t is 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. Integer factorization algorithms