View source for Schoof’s point-counting algorithm

'''René Schoof's point counting algorithm''' <ref>René Schoof. ''Mathematics of Computation,'' vol. 44. no. 170
April 1985. pp. 483–494. https://www.ams.org/journals/mcom/1985-44-170/S0025-5718-1985-0777280-6/S0025-5718-1985-0777280-6.pdf</ref> 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 4''g''√''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]] ''φ''&nbsp;:&nbsp;(''x'',''y'')&nbsp;→&nbsp;(''x''<sup>''q''</sup>,''y''<sup>''q''</sup>) is proven to satisfy the characteristic equation ''φ''<sup>2</sup>&nbsp;‑&nbsp;''tφ''&nbsp;+&nbsp;''q''&nbsp;=&nbsp;0 with ''t''&nbsp;=&nbsp;''q''&nbsp;+&nbsp;1&nbsp;‑&nbsp;♯''E''<sub>'''Z'''/''q'''''Z'''</sub>.

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 <nowiki>[</nowiki>‑2''g''√''q'',2''g''√''q''<nowiki>]</nowiki> so that ♯''E''<sub>'''Z'''/''q'''''Z'''</sub>&nbsp;=&nbsp;''q''&nbsp;+&nbsp;1&nbsp;‑&nbsp;''t''.

== Schoof–Elkies–Atkin (SEA) ==

[https://en.wikipedia.org/wiki/Schoof%E2%80%93Elkies%E2%80%93Atkin_algorithm 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]].