Other Applications - Elliptic Curves: Number Theory and Cryptography - page 195

should also include proofs of primality of each of these primes .Andwe
should include proofs of primality of the auxiliary primes used in the proofs
for each , etc. Anyone can use this information to verify our proof. We never
need to say how we found the numbers a , nor how we factored r .

What happens if we cannot find enough factors of n − 1toobtain r ≥ √ n
such that we know all the prime factors of r ? This is clearly a possibility if
we are working with n of a thousand digits. As in the case of the p− 1factoring
method in Section 7.1, an elliptic curve analogue comes to the rescue. Note
that the number n − 1 that we need to factor is the order of the group Z n .If
we can use elliptic curves, we can replace n− 1 with a group order near n , but
there will be enough choices for the elliptic curve that we can probably find
a number that can be partially factored. The following is due to Goldwasser
and Kilian [47]. Recall that a finite point in E ( Z n )isapoint( x, y )with
x, y ∈ Z n . This is in contrast to the points in E ( Z n ) that are infinite mod

some of the factors of n and therefore cannot be expressed using coordinates
in Z n . See Section 2.10.

THEOREM 7.3
Let n> 1 and let E be an ellipticcurvemod n .Supposethere exist distinct
primenumbers 1 ,..., k and finitepoints P i ∈ E ( Z n ) su ch that

1. i P i =

k
2. i =1 i > n 1 / 4 +1 2 .

∞ for 1 ≤ i ≤

Then n isprime.

Let p be a prime factor of n .Write n = p f n 1 with p n 1 .Then PROOF

E ( Z n )= E ( Z p f ) ⊕ E ( Z n 1 ) .

Since P i is a finite point in E ( Z n ), it yields a finite point in E ( Z p f ), namely
P i mod p f . We can further reduce and obtain a finite point P i,p = P i mod p
in E ( F p ). Since i P i = mod every factor of n .

In particular, i P i,p = ∞ in E ( F p ), which means that P i,p has order i .It
follows that

∞ mod n ,wehave i P i = ∞

# E ( F p )
for all i ,so# E ( F p ) is divisible by i . Therefore,

i |

n 1 / 4 +1 2

i ≤ # E ( F p ) <p +1+2 √ p = p 1 / 2 +1 2

k

< ,

i =1

so p> √ n . Since all prime factors of n are greater than √ n , it follows that n
is prime.