Cryptography Reference
In-Depth Information
P rime N umbers
A prime number is any positive integer greater than 1 that is
divisible only by itself and 1; e.g., 2, 3, 5, 7, 11, 13, 17, 19, 23, ….
A key result of number theory, called the fundamental the-
orem of arithmetic, states that every positive integer greater
than 1 can be expressed as the product of prime numbers in a
unique fashion. Because of this, primes can be regarded as the
multiplicative “building blocks” for the natural numbers (all
whole numbers greater than zero; e.g., 1, 2, 3, …).
Primes have been recognized since antiquity, when they
were studied by the Greek mathematicians Euclid (fl. c. 300
bce ) and Eratosthenes of Cyrene (c. 276-194 bce ), among oth-
ers. In his Elements , Euclid gave the first known proof that
there are infinitely many primes. Various formulas have been
suggested for discovering primes, but all have been flawed.
Two other famous results concerning the distribution of prime
numbers merit special mention: the prime number theorem
and the Riemann zeta function.
Since the late 20th century, with the help of computers,
prime numbers with millions of digits have been discovered.
Like efforts to generate ever more digits of π , such number
theory research was thought to have no possible application—
that is, until cryptographers discovered how large primes
could be used to make nearly unbreakable codes.
apt to change, in a cryptosecure way, half of the bits in the
digest. By cryptosecure is meant that it is computationally
infeasible for anyone to find a message that will produce
a preassigned digest and equally hard to find another
message with the same digest as a known one. To sign
a message—which may not even need to be kept secret—
A encrypts the digest with the secret e , which he appends
to the message. Anyone can then decrypt the message
 
Search WWH ::




Custom Search