Elliptic Curves: Algorithms
Date: 03/11/99 at 02:35:04 From: Mark Pineda Subject: Elliptic curve factoring If the family of elliptic curves is defined by y^2 = x^3 + 1, how do we find the number of points on the curve over F sub p?
Date: 03/11/99 at 16:24:59 From: Doctor Rob Subject: Re: Elliptic curve factoring Two things before we begin. First, the above equation is a single curve, not a family of curves. Secondly, you are asking how to find the number of points on this curve, but your subject is "Elliptic curve factoring." These two are not the same thing. Hasse's Theorem says that if N is the number of points, then p + 1 - 2*sqrt(p) < N < p + 1 + 2*sqrt(p). If p is small you can actually try all values of x, and find which ones give x^3 + 1 a quadratic residue modulo p. Those that do will give two points (x,sqrt[x^3+1]) and (x,-sqrt[x^3+1]). Those that do not will give no points. Of course, those that give x^3 + 1 = 0 (there are 0, 1, or 3 of them) will give a single point (x,0). Count them all up, and you will have N. If N is not in the above range, you have missed some. This can work for values of p up to, perhaps, 10^6. The method to try next if p is too large to do the above, is to use the Shanks Baby-Step-Giant-Step Algorithm. This depends on the following. The points on the curve modulo p form a finite abelian group, and Lagrange's Theorem says that the order of the group times any element must be the identity. Take a point P on the curve. (This is not too tough. Pick a value of x, and test whether x^3 + 1 is a square. Your chance of success is very close to 1/2. If not, throw that x away and try again. After just a few trials, you will find a successful value of x. If it is a square, find its square root, and let that be y, and you have your point P.) Let L be 2*p^(1/4), rounded up to the next integer. Compute P(k) = k*P, k = 1, 2, 3, ... L Here, this involves adding points on the elliptic curve, using the group law for this operation in the group of points. If any of the P(k)'s is 0, the identity of the group, then you have found the order m <= L of P. If not, put these in a table and sort it. Also compute Q(i) = (p+1-L^2)*P + i*(L*P) for i = 0, 1, ..., L. Put these into another table and sort it, too. Now look for a point in both tables. Then for each such match you have k*P = (p+1-L^2)*P + i*(L*P), O = (p + 1 - L^2 + i*L - k)*P. This implies that the order m of the element P in the group of points is a divisor of p + 1 - L^2 + i*L - k, and so it is a divisor of the GCD of these values for each such match. It is also a divisor of N. If you can factor this GCD completely, you can determine the exact value of m; then N must be a multiple of m. If m is not too small, there will be a feasible number of possibilities for N in the above range, sometimes only one. If m is too small (and this can happen: P = (-1,0) has m = 2, for example), you should discard P, pick a different one, and try again. If you cannot factor this GCD completely, write it in the form M*R, where M is completely factored, and R is composite but not factored. Then you can determine the smallest multiple of R that is also a multiple of m. It is very likely, but not sure, that m will equal this number. This will give you a value for N which has a small probability of being incorrect. This works for p up to perhaps 10^24. If p is too large to do either of the above computations, then you have to resort to something called Schoof's Algorithm, which determines N modulo q for several small primes q, and then combines this information using the Chinese Remainder Theorem. If the product of these small primes is > 4*sqrt(p), then there is just one number in the above range which is in the resulting congruence class, so that must be N. If you need more information about Schoof's Algorithm, write again and I will try to explain it. - Doctor Rob, The Math Forum http://mathforum.org/dr.math/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.