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

is an isomorphism from E ns = E ( Z n ) (0 , 0) to Z n , regarded as an additive

group. A random point P in E ns corresponds to a random integer a mod
n .

\

Computing ( B !) P corresponds to computing ( B !) a (mod n ). We have

( B !) P = ∞ (mod p ) if and only if ( B !) a ≡ 0(mod p ), which occurs if and

only if p 1be B -

smooth). Essentially, this reduces to the easiest factorization method: divide
n byeachoftheprimesupto B . This method is impractical if the smallest
prime factor of n is not small. But at least it is almost an ecient way to
do it. If we replace B ! by the product Q of primes up to B , then computing
gcd( Q, n ) is often faster than trying each prime separately.

≤ B (note that this is much less likely than having p −

7.2 Primality Testing

Suppose n is an integer of several hundred decimal digits. It is usually
easy to decide with reasonable certainty whether n is prime or composite.
But suppose we actually want to prove that our answer is correct. If n is
composite, then usually either we know a nontrivial factor (so the proof that
n is composite consists of giving the factor) or n failed a pseudoprimality test
(for example, perhaps a n− 1 ≡ 1(mod n )forsome a ). Therefore, when n

is composite, it is usually easy to prove it, and the proof can be stated in
a form that can be checked easily. But if n is prime, the situation is more
di cult. Saying that n passed several pseudoprimality tests indicates that n
is probably prime, but do es not prove that n is prime. Saying that a computer

checked all primes up to √ n is not very satisfying (and is not believable when n
has several hundred digits). Cohen and Lenstra developed methods involving
Jacobi sums that work well for primes of a few hundred digits. However, for
primes of a thousand digits or more, the most popular method currently in use
involves elliptic curves. ( Note : For primes restricted to special classes, such
as Mersenne primes, there are special methods. However, we are considering
randomly chosen primes.)
The elliptic curve primality test is an elliptic curve version of the classical
Pocklington-Lehmer primality test . Let's look at it first.

PROPOSITION 7.1
Let n> 1 be an integer, and let n ≥ √ n .Supposethat,for − 1= rs with r

each prime

| r ,there existsaninteger a with

≡ 1(mod n ) and gcd a ( n− 1) / − 1 ,n =1 . a n− 1

Then n isprime.