Schoof’s point-counting algorithm

René Schoof's point counting algorithm determines the exact number of points on an elliptic curve within the range determined by Hasse’s theorem.

The algorithm runs in polynomial time. It is alarming, or should be, to users of cryptographic schemes that depend on the difficulty of solving the discrete logarithm problem over elliptic curves, that a problem once requiring baby-step giant-step or similar algorithms was suddenly solved in polynomial time.

Schoof–Elkies–Atkin (SEA) is an improved variant which is much more efficient, of Las Vegas type expected termination.

Such an easy method of calculating the order of an elliptic curve over a finite field, that is, the exact number of points on it, might lead to easy solutions for the discrete logarithm problem in general, and we should assume this to be the case, especially in light of redactions of published information from certain European axis-aligned non-U.S. and “ex-pat” sources, unless there are good explanations why this is not so.

Elliptic Curve Crypto:General disclaimer.