Schoof's algorithm: Difference between revisions

Revision as of 13:36, 2 September 2024

Latest revision as of 18:30, 21 June 2025

(6 intermediate revisions by 3 users not shown)

Line 1:

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

'''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 81 ⟶ 82:

: <math>

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

</math>

Line 87 ⟶ 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 160 ⟶ 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==