Content deleted Content added
→The algorithm: elaborate on the use of the Chinese Remainder Theorem |
m revision for accuracy and clarity →Case 1: (x^{q^{2}}, y^{q^{2}}) \neq \pm \bar{q}(x, y) |
||
| (34 intermediate revisions by 21 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 8 ⟶ 9:
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>
y^2 = x^3 + Ax + B
</math>
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 41 ⟶ 42:
One could try to symbolically compute these points <math>(x^{q^{2}}, y^{q^{2}})</math>, <math>(x^{q}, y^{q})</math> and <math>q(x, y)</math> as functions in the [[Imaginary hyperelliptic curve#Coordinate ring|coordinate ring]] <math>\mathbb{F}_{q}[x,y]/(y^{2}-x^{3}-Ax-B)</math> of <math>E</math>
and
Schoof's idea was to carry out this computation restricted to points of order <math>l</math> for various small primes <math>l</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 100 ⟶ 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>
Line 107 ⟶ 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>.
==The algorithm==
Input:
1. An elliptic curve <math>E = y^{2}-x^{3}-Ax-B</math>.
2. An integer {{mvar|q}} for a finite field <math>F_q</math> with <math>q=p^{b}, b \ge 1</math>.
Output:
The number of points of {{mvar|E}} over <math>F_q</math>.
Choose a set of odd primes {{mvar|S}} not containing {{mvar|p}} {{nowrap|such that <math>N=\prod_{l\in S} l > 4\sqrt{q}.</math>}}
{{nowrap|'''Put''' <math>t_2=0</math> '''if''' <math>\gcd(x^{q}-x, x^{3} + Ax + B)\neq 1</math>, '''else''' <math>t_2=1</math>.}}
Line 141 ⟶ 145:
{{nowrap|<math>t_{l}=0</math>}}
Use the [[Chinese Remainder Theorem]] to compute {{mvar|t}} modulo {{mvar|N}}
from the equations <math>
Output <math>q+1-t</math>.
Line 152 ⟶ 156:
In the 1990s, [[Noam Elkies]], followed by [[A. O. L. Atkin]], devised improvements to Schoof's basic algorithm by restricting the set of primes <math>S = \{l_1, \ldots, l_s\}</math> considered before to primes of a certain kind. These came to be called Elkies primes and Atkin primes respectively. A prime <math>l</math> is called an Elkies prime if the characteristic equation: <math>\phi^2-t\phi+ q = 0</math> splits over <math>\mathbb{F}_l</math>, while an Atkin prime is a prime that is not an Elkies prime. Atkin showed how to combine information obtained from the Atkin primes with the information obtained from Elkies primes to produce an efficient algorithm, which came to be known as the [[Schoof–Elkies–Atkin algorithm]]. The first problem to address is to determine whether a given prime is Elkies or Atkin. In order to do so, we make use of modular polynomials, which come from the study of [[modular forms]] and an interpretation of [[Elliptic curve#Elliptic curves over the complex numbers|elliptic curves over the complex numbers]] as lattices. Once we have determined which case we are in, instead of using [[division polynomials]], we are able to work with a polynomial that has lower degree than the corresponding division polynomial: <math>O(l)</math> rather than <math>O(l^2)</math>. For efficient implementation, probabilistic root-finding algorithms are used, which makes this a [[Las Vegas algorithm]] rather than a deterministic algorithm.
Under the heuristic assumption that approximately half of the primes up to an <math>O(\log q)</math> bound are Elkies primes, this yields an algorithm that is more efficient than Schoof's, with an expected running time of <math>O(\log^6 q)</math> using naive arithmetic, and <math>\tilde{O}(\log^4 q)</math> using fast arithmetic.
==Implementations==
Several algorithms were implemented in [[C++]] by Mike Scott
* Schoof's algorithm [
* Schoof's algorithm [
==See also==
Line 175 ⟶ 179:
{{Number-theoretic algorithms}}
{{Algebraic curves navbox}}
[[Category:Asymmetric-key algorithms]]
| |||