Cryptography Reference
In-Depth Information
Example 7.3
Let n = 907. Let E be the elliptic curve y 2 = x 3 +10 x
2mod n .Let = 71.
Then
> 907 1 / 4 +1 2
42 . 1 .
Let P = (819 , 784). Then 71 P = . Theorem 7.3 implies that 907 is prime.
Of course, we needed the fact that 71 is prime, which could also be proved
using Theorem 7.3, or by direct calculation.
How did we find E and P ? First, we looked at a few elliptic curves mod 907
until we found one whose order was divisible by a prime that was slightly
larger than 42 . 1. (If we had chosen
907 then we wouldn't have made much
progress, since we would still have needed to prove the primality of ). In fact,
to find the order of the curve, we started with curves where we knew a point.
In the present case, E has the point (1 , 3). Using Baby Step, Giant Step, we
found the order of (1 , 3) to be 923 = 13 · 71. Then we took P = 13(1 , 3), which
has order 71.
For large n , the hardest part of the algorithm is finding an elliptic curve
E with a suitable number of points. One possibility is to choose random
elliptic curves mod n and compute their orders, for example, using Schoof's
algorithm, until an order is found that has a suitable prime factor .Amore
e cient procedure, due to Atkin and Morain (see [7]), uses the theory of
complex multiplication to find suitable curves.
As in the Pocklington-Lehmer test, once a proof of primality is found, it
can be recorded rather compactly. The Goldwasser-Kilian test has been used
to prove the primality of numbers of more than 1000 decimal digits.
Exercises
7.1 Let E be y 2 = x 3
20 x + 21 mod 35, and let P =(15 , − 4).
(a)Factor35bytryingtocompute3 P .
(b)Factor35bytryingtocompute4 P by doubling twice.
(c) Compute both 3 P and 4 P on E mod 5 and on E mod 7. Explain
why the factor 5 is obtained by computing 3 P and 7 is obtained by
computing 4 P .
7.2 This exercise shows that when the elliptic curve factorization method is
applied to the singular curve y 2 = x 2 ( x + a )where a is not a square mod
aprime p , then we obtain a method equivalent to the p + 1 factoring
method [134]. We first describe a version of the p +1 method. Let p be
an odd prime factor of the integer n that we want to factor. Let t 0 =2
and choose a random integer t 1 mod n . Define t m by the recurrence
Search WWH ::




Custom Search