Schoof’s point-counting algorithm

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

The algorithm is claimed to run 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.

Main plan of attack

A collection of distinct small primes is chosen, enough that their product exceeds the range of 4g√q determined by Hasse’s theorem, depending on the genus g of the curve E over the field of prime order and characteristic q.

The Frobenius endomorphism φ : (x,y) → (x^q,y^q) is proven to satisfy the characteristic equation φ² ‑ tφ + q = 0 with t = q + 1 ‑ ♯E_Z/qZ.

The main idea presented by René Schoof is to solve this characteristic equation modulo ℓ for each of the small primes ℓ, and then combine the solutions using the Chinese remainder theorem to determine t uniquely within the range [‑2g√q,2g√q] so that ♯E_Z/qZ = q + 1 ‑ t.

Schoof–Elkies–Atkin (SEA)

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.