Schoof's algorithm: Difference between revisions

Revision as of 17:02, 7 January 2019

Latest revision as of 18:30, 21 June 2025

(11 intermediate revisions by 8 users not shown)

Line 1:

{{Short description|Efficient algorithm to count points on elliptic curves}}

==Introduction==

'''Schoof's algorithm''' is an efficient algorithm to count points on [[elliptic curve]]s over [[finite fields]]. The algorithm has applications in [[elliptic curve cryptography]] where it is important to know the number of points to judge the difficulty of solving the [[discrete logarithm problem]] in the [[Group (mathematics)|group]] of points on an elliptic curve.

Line 6:

This article explains Schoof's approach, laying emphasis on the mathematical ideas underlying the structure of the algorithm.

==Introduction==

Let <math>E</math> be an [[elliptic curve]] defined over the finite field <math>\mathbb{F}_{q}</math>, where <math>q=p^n</math> for <math>p</math> a prime and <math>n</math> an integer <math>\geq 1</math>. Over a field of characteristic <math>\neq 2, 3</math> an elliptic curve can be given by a (short) Weierstrass equation

: <math>

Line 13:

with <math>A,B\in \mathbb{F}_{q}</math>. The set of points defined over <math>\mathbb{F}_{q}</math> consists of the solutions <math>(a,b)\in\mathbb{F}_{q}^2</math> satisfying the curve equation and a [[point at infinity]] <math>O</math>. Using the [[Elliptic curve#The group law|group law]] on elliptic curves restricted to this set one can see that this set <math>E(\mathbb{F}_{q})</math> forms an [[abelian group]], with <math>O</math> acting as the zero element.

In order to count points on an elliptic curve, we compute the cardinality of <math>E(\mathbb{F}_{q})</math>.

Schoof's approach to computing the cardinality <math>\sharp# E(\mathbb{F}_{q})</math> makes use of [[Hasse's theorem on elliptic curves]] along with the [[Chinese remainder theorem]] and [[division polynomials]].

==Hasse's theorem==

Line 30:

Given the elliptic curve <math>E</math> defined over <math>\mathbb{F}_{q}</math> we consider points on <math>E</math> over <math>\bar{\mathbb{F}}_{q}</math>, the [[algebraic closure]] of <math>\mathbb{F}_{q}</math>; i.e. we allow points with coordinates in <math>\bar{\mathbb{F}}_{q}</math>. The [[Frobenius endomorphism]] of <math>\bar{\mathbb{F}}_{q}</math> over <math>\mathbb{F}_q</math> extends to the elliptic curve by <math> \phi : (x, y) \mapsto (x^{q}, y^{q})</math>.

This map is the identity on <math>E(\mathbb{F}_{q})</math> and one can extend it to the point at infinity <math>O</math>, making it a [[group morphism]] from <math>E(\bar{\mathbb{F}}_{q}})</math> to itself.

The Frobenius endomorphism satisfies a quadratic polynomial which is linked to the cardinality of <math>E(\mathbb{F}_{q})</math> by the following theorem:

Line 82:

: <math>

(x^3+Ax+B)((x^3+Ax+B)^{\frac{q^{2}-1}{2}}-\theta(x))^2

</math>

Line 88:

: <math>

X(x)\equiv (x^3+Ax+B)\left(\frac{(x^3+Ax+B)^{\frac{q^{2}-1}{2}}-\theta(x)}{x^{q^2}-x_{\bar{q}}}\right)^2\bmod \psi_l(x).

</math>

Here, it seems not right, we throw away <math>x^{q^{2}}-x_{\bar{q}}</math>?

Now if <math>X \equiv x^{q} _ {\bar{t}}\bmod \psi_l(x)</math> for onesome <math>\bar{t}\in [0,(l-1)/2]</math>, then <math>\bar{t}</math> satisfies

: <math>

Line 161 ⟶ 159:

==Implementations==

Several algorithms were implemented in [[C++]] by Mike Scott and are available with [ftp://ftp.computing.dcu.ie/pub/crypto/ source code]. The implementations are free (no terms, no conditions), and make use of the [https://web.archive.org/web/20121114015633/http://certivoxgithub.com/solutions/miracl-crypto-sdk/MIRACL MIRACL] library which is distributed under the [[AGPLv3]].

* Schoof's algorithm [ftphttps://ftpgithub.computing.dcu.iecom/miracl/MIRACL/blob/master/pubsource/cryptocurve/schoof.cpp implementation] for <math>E(\mathbb{F}_p)</math> with prime <math>p</math>.

* Schoof's algorithm [ftphttps://ftpgithub.computing.dcu.iecom/miracl/MIRACL/blob/master/pubsource/cryptocurve/schoof2.cpp implementation] for <math>E(\mathbb{F}_{2^m})</math>.

==See also==

Line 181 ⟶ 179:

{{Number-theoretic algorithms}}

{{Algebraic curves navbox}}

[[Category:Asymmetric-key algorithms]]