Content deleted Content added
m revision for accuracy and clarity →Case 1: (x^{q^{2}}, y^{q^{2}}) \neq \pm \bar{q}(x, y) |
|||
| (23 intermediate revisions by 17 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 The algorithm was published by [[René Schoof]] in 1985 and it was a theoretical breakthrough, as it was the first deterministic polynomial time algorithm for [[counting points on elliptic curves]]. Before Schoof's algorithm, approaches to counting points on elliptic curves such as the naive and [[baby-step giant-step]] algorithms were, for the most part, tedious and had an exponential running time.
Line 12 ⟶ 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>\
==Hasse's theorem==
{{main|Hasse's theorem on elliptic curves}}
Hasse's theorem states that if <math>E/\mathbb{F}_{q}</math> is an elliptic curve over the finite field <math>\mathbb{F}_{q}</math>, then <math>\
: <math>
\mid q + 1 - \
</math>
This powerful result, given by Hasse in 1934, simplifies our problem by narrowing down <math>\
In order to compute <math>t \pmod l</math> for a prime <math>l \neq p</math>, we make use of the theory of the Frobenius endomorphism <math>\phi</math> and [[division polynomials]]. Note that considering primes <math>l \neq p</math> is no loss since we can always pick a bigger prime to take its place to ensure the product is big enough. In any case Schoof's algorithm is most frequently used in addressing the case <math>q=p</math> since there are more efficient, so called <math>p</math> adic algorithms for small-characteristic fields.
Line 29 ⟶ 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
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 35 ⟶ 36:
'''Theorem:''' The Frobenius endomorphism given by <math>\phi</math> satisfies the characteristic equation
: <math> \phi ^2 - t\phi + q = 0,</math> where <math> t = q + 1 - \
Thus we have for all <math>P=(x, y) \in E</math> that <math>(x^{q^{2}}, y^{q^{2}} ) + q(x, y) = t(x^{q}, y^{q})</math>, where + denotes addition on the elliptic curve and <math>q(x,y)</math> and <math>t(x^{q},y^{q})</math>
Line 67 ⟶ 68:
We must split the problem into two cases: the case in which <math>(x^{q^{2}}, y^{q^{2}}) \neq \pm \bar{q}(x, y)</math>, and the case in which <math>(x^{q^{2}}, y^{q^{2}}) = \pm \bar{q}(x, y)</math>. Note that these equalities are checked modulo <math>\psi_l</math>.
By using the [[Elliptic curves#The group law|addition formula]] for the group <math>E(\mathbb{F}_{q})</math> we obtain:
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>
Now if <math>X \equiv x^{q} _ {\bar{t}}\bmod \psi_l(x)</math> for
: <math>
Line 102 ⟶ 101:
As mentioned earlier, using {{mvar|Y}} and <math>y_{\bar{t}}^{q}</math> we are now able to determine which of the two values of <math>\bar{t}</math> (<math>\bar{t}</math> or <math>-\bar{t}</math>) works. This gives the value of <math>t\equiv \bar{t}\pmod l</math>. Schoof's algorithm stores the values of <math>\bar{t}\pmod l</math> in a variable <math>t_l</math> for each prime {{mvar|l}} considered.
We begin with the assumption that <math>(x^{q^{2}}, y^{q^{2}}) = \bar{q}(x, y)</math>. Since {{mvar|l}} is an odd prime it cannot be that <math>\bar{q}(x, y)=-\bar{q}(x, y)</math> and thus <math>\bar{t}\neq 0</math>. The characteristic equation yields that <math>\bar{t} \phi(P) = 2\bar{q} P</math>. And consequently that <math>\bar{t}^{2}\bar{q} \equiv (2q)^{2} \pmod l</math>
This implies that {{mvar|q}} is a square modulo {{mvar|l}}. Let <math>q \equiv w^{2} \pmod l</math>. Compute <math>w\phi(x,y)</math> in <math>\mathbb{F}_{q}[x,y]/(y^{2}-x^{3}-Ax-B, \psi_{l})</math> and check whether <math>
\bar{q}(x, y)=w\phi(x,y)</math>. If so, <math>t_{l}</math> is <math>\pm 2w \pmod l</math> depending on the y-coordinate.
Line 109 ⟶ 108:
If {{mvar|q}} turns out not to be a square modulo {{mvar|l}} or if the equation does not hold for any of {{mvar|w}} and <math>-w</math>, our assumption that <math>(x^{q^{2}}, y^{q^{2}}) = +\bar{q}(x, y)</math> is false, thus <math>(x^{q^{2}}, y^{q^{2}}) = - \bar{q}(x, y)</math>. The characteristic equation gives <math>t_l=0</math>.
If you recall, our initial considerations omit the case of <math>l = 2</math>.
Since we assume {{mvar|q}} to be odd, <math>q + 1 - t \equiv t \pmod 2</math> and in particular, <math>t_{2} \equiv 0 \pmod 2</math> if and only if <math>E(\mathbb{F}_{q})</math> has an element of order 2. By definition of addition in the group, any element of order 2 must be of the form <math>(x_{0}, 0)</math>. Thus <math>t_{2} \equiv 0 \pmod 2</math> if and only if the polynomial <math>x^{3} + Ax + B</math> has a root in <math>\mathbb{F}_{q}</math>, if and only if <math>\gcd(x^{q}-x, x^{3} + Ax + B)\neq 1</math>.
Line 160 ⟶ 159:
==Implementations==
Several algorithms were implemented in [[C++]] by Mike Scott
* Schoof's algorithm [
* Schoof's algorithm [
==See also==
Line 180 ⟶ 179:
{{Number-theoretic algorithms}}
{{Algebraic curves navbox}}
[[Category:Asymmetric-key algorithms]]
| |||