Cryptography Reference
In-Depth Information
Chapter 7
Other Applications
In the 1980s, about the same time that elliptic curves were being introduced
into cryptography, two related applications of elliptic curves were found, one
to factoring and one to primality testing. These are generalizations of classical
methods that worked with multiplicative groups
Z
n
. The main advantage of
elliptic curves stems from the fact that there are many elliptic curves mod a
number
n
, so if one elliptic curve doesn't work, another can be tried.
The problems of factorization and primality testing are related, but are
very different in nature. The largest announced factorization up to the year
2007 was of an integer with 200 digits. However, it was at that time possible
to prove primality of primes of several thousand digits.
It is possible to prove that a number is composite without finding a factor.
One way is to show that
a
n−
1
1(mod
n
)forsome
a
with gcd(
a, n
)=1.
Fermat's little theorem says that if
n
is prime and gcd(
a, n
)=1,then
a
n−
1
≡
1
(mod
n
), so it follows that
n
must be composite, even though we have not
produced a factor. Of course, if
a
n−
1
≡
1(mod
n
) for several random choices
of
a
, we might suspect that
n
is probably prime. But how can we actually
prove
n
is prim
e
? If
n
has only a few digits, we can divide
n
by each of the
≡
primes up to
√
n
. However, if
n
has hundreds of digits, this method will take
too long (much longer than the predicted life of the universe). In Section 7.2,
we discuss ecient methods for proving primality. Similarly, suppose we have
proved that a number is composite. How do we find the factors? This is a
di
cult computational problem. If the smallest prime fa
ct
or of
n
has more
than a few digits, then trying all prime factors up to
√
n
cannot work. In
Section 7.1, we give a method that works well on numbers
n
of around 60
digits.
7.1 Factoring Using Elliptic Curves
In the mid 1980s, Hendrik Lenstra [75] gave new impetus to the study of
elliptic curves by developing an e
cient factoring algorithm that used elliptic
Search WWH ::
Custom Search