Transcript PowerPoint Presentation - Named and Notorious Primes

Named and Notorious Primes
Joe Frost
University of Washington
Computing and
Communications
Joyce Frost
Lake Washington High
School
Prime Numbers
“Prime numbers are the very atoms of
arithmetic. . . The primes are the jewels
studded throughout the vast expanse of the
infinite universe of numbers that
mathematicians have studied down the
centuries.” Marcus du Sautoy, The Music of
the Primes
A History and Exploration of
Prime Numbers
Dedicated to Royal Penewell -1923-2008
Math Teacher and Prime Enthusiast
QuickTime™ and a
TIFF (Uncompressed) decompressor
are needed to see this picture.
Named and Notorious Primes
•
•
•
•
Early Primes
Named Primes
Hunting for Primes
Harnessing Primes
Euclid of Alexandria
325-265 B.C.
• The only man to summarize all
the mathematical knowledge of
his times.
• In Proposition 20 of Book IX of
the Elements, Euclid proved
that there are infinitely many
prime numbers.
QuickTime™ and a
TIFF (Uncompressed) decompressor
are needed to see this picture.
Eratosthenes of Cyrene
276-194 B.C.
• Librarian of the University of Alexandria.
• Invented an instrument for duplicating the
cube, measured the circumference of the
Earth, calculated the distance from the Earth
to the Sun and the Moon, and created an
algorithm for finding all possible primes,
the Eratosthenes Sieve.
Nicomachus of Gerasa
c. 100 A.D.
• Introduction to Arithmetic, Chapters XI, XII, and
XIII divide odd numbers into three categories,
“prime and incomposite”, “composite”, and “the
number which is in itself secondary and
composite, but relatively to another number is
prime and incomposite.”
• In chapter XIII he describes Eratosthenes’ Sieve in
excruciating detail.
Pierre de Fermat
1601-1665
• Fermat’s Little Theorem - If a is any whole
number and p is a prime that is not a factor
of a, then p must be a factor of the number
(ap-1-1).
• Mentioned in a letter in 1640 with no proof,
proved by Euler in 1736
Leonhard Euler
1707-1783
• Euler proved a stronger version of Fermat’s
Little Theorem to help test for Euler
Probable Primes:
“If p is prime and a is any whole
number, then p divides evenly into ap-a.”
Carl Friedrich Gauss
1777-1855
• At 15, he received a table of logarithms and
one of primes for Christmas
• He noticed that primes are distributed to
approximately π(N) ~ N/log(N), now called
The Prime Number Theorem
• First mentioned it in a letter 50 years later.
Bernhard Riemann
1826-1866
• One of the million-dollar problems is the
Riemann Hypothesis: "All non-trivial zeros
of the zeta function have real part of one
half."
• ζ(s) = ∑ (n-s) (n=1,2,3,…)
or
• ζ(s) =∏(ns)/(ns -1) (n=2,3,5,7,11,…)
Named and Notorious Primes
•
•
•
•
Early Primes
Named Primes
Hunting for Primes
Harnessing Primes
Absolute Prime
Also called permutable prime, an absolute
prime is a prime with at least two distinct
digits which remains prime on every
rearrangement (permutation) of the digits. For
example, 337 is a permutable because each
of 337, 373 and 733 are prime. Most likely, in
base ten the only permutable primes are 13,
17, 37, 79, 113, 199, 337, and their
permutations.
Cullen Primes
Fr. James Cullen, SJ, was interested in the
numbers n*2n +1 (denoted Cn). He noticed
that the first, C1=3, was prime, but with the
possible exception of the 53rd, the next 99
were all composite. Later, Cunningham
discovered that 5591 divides C53, and noted
these numbers are composite for all n in the
range 2 < n < 200, with the possible
exception of 141.
Cullen Primes of the Second
Kind
• Five decades later Raphael Robinson
showed C141 was a prime. The only known
Cullen primes Cn are those with n=1, 141,
4713, 5795, 6611, 18496, 32292, 32469,
59656, 90825, 262419, 361275, and 481899.
• These numbers are now called the Cullen
numbers. Sometimes, the name "Cullen
number" is extended to also include the
Woodall numbers: Wn=n*2n -1. These are
then the "Cullen primes of the second kind".

Fermat Primes
• Fermat numbers are numbers of the form
2n
2 1
• Fermat believed every Fermat number is
prime. Fn is prime for n  0,1,2,3,4,?
• Fn is composite for 4 < n < 31, but no one
knows if there are infinitely many Fermat

Primes.
Euler PRP
• Euler was able to prove a stronger
statement of Fermat’s Little Theorem
which he then used as to test for Euler
probable primes.
• If an Euler PRP n is composite, then we
say n is an Euler pseudoprime.
Ferrier’s Prime
• Ferrier’s Prime is the largest prime found
before electronic calculators. Ferrier’s
Prime = 1/17(2148+1) =
20988936657440586486151264256610222
593863921
Fibonacci Prime
• A Fibonacci prime is a Fibonacci
number that is prime.
• 1,1,2,3,5,8,13,21,34,55,89,144…
Sophie Germain Prime
• A Sophie Germain prime is a prime p such that
q=2p+1 is also prime - (2, 3, 5, 11, 23, …)
• Around 1825, Sophie Germain proved that the
first case of Fermat's last theorem is true for such
primes, i.e., if p is a Sophie Germain prime, then
there do not exist integers x, y, and z different
from 0 and none a multiple of p such that
xp+yp=zp.
Goldbach’s Conjecture
• “Every even number is a sum of two
primes.”
• Has been verified for all even numbers to
400 trillion, but not yet proved.
Illegal Primes
Phil Carmody published the first known
illegal prime. When converted to
hexadecimal, the number is a compressed
form of the computer code to crack CSS
scrambling. It is "illegal" because
publishing this number could be considered
trafficking in a circumvention device, in
violation of the Digital Millenium
Copyright Act.
Lucas Prime
• A Lucas prime is a Lucas number
that is prime. The Lucas numbers
can be defined as follows: v1 = 1,
v2 = 3 and v n+1 = vn + v n-1 (n > 2)
• Lucas numbers are like Fibonacci
numbers, except that they start with 1
and 3 instead of 1 and 1.
Mersenne Prime
• Mersenne primes are the primes of the
form 2n–1. Mersenne claimed that n in
{2,3,5,7,13,19,31,67,127,257} would
yield primes
• A Gaussian Mersenne prime is a prime
using Gaussian integers (1, -1, i, -i).
Landry and Aurifeuille
• The mathematician Landry devoted a good
part of his life to factoring 2n+1 and finally
found the factorization of 258+1 in 1869 (so he
was essentially the first to find the Gaussian
Mersenne with n=29).
• Just ten years later, Aurifeuille found the
Gaussian factorization, which would have
made Landry's massive effort trivial.
Lucas-Lehmer Number
The Lucas-Lehmer test is an efficient
deterministic primality test for determining
if a Mersenne number M_n is prime. A
Mersenne Number 2n -1 is prime if it
divides the Lucas-Lehmer number Ln where
Ln=(Ln-1)2-2
Palindromic Prime
• A palindromic prime is a prime that is a palindrome.
of palindromic primes by G. L. Honaker, Jr.
2
30203
133020331
1713302033171
12171330203317121
151217133020331712151
1815121713302033171215181
16181512171330203317121518161
331618151217133020331712151816133
• Largest known is 105901146541059011
A pyramid
Royal Prime
Royal Primes are primes where the
digits are all prime and a prime can be
constructed through addition or
subtraction using all the digits. These
are named after Royal Penewell,
treasurer of the Puget Sound Council of
Teachers of Mathematics (PSCTM)
from 1973 to 2005 and who was born in
`23, the first Royal Prime of the century.
Repunit Primes
• Repunits are positive integers in which all the
digits are 1, denoted as R1 = 1, R2=11, etc. Of
these, the following are known to be prime:11,
1111111111111111111, and
11111111111111111111111 (2, 19, and 23 digits),
R317 (10317-1)/9, and R1,031 (101031-1)/9.
• In 1999 Dubner discovered that R49081 =
(1049081-1)/9 was a probable prime, in 2000
Baxter discovered the next repunit probable prime
is R86453, and in 2007 Dubner identified R109297 as
a probable prime.
Twin Primes
• Twin Primes are primes whose difference is
2.
• Conjectured but not proven that there are an
infinite number of twin primes.
• All twin primes except (3, 5) are of the form
6n+/-1.
• 2486!!!!+/-1 are twin primes with 2151
digits
Cousin Primes
• Cousin primes are primes whose difference
is 4.
• The first few pairs are
{3,7},{7,11},{17,23},{43,47}
Sexy Primes
• Sexy primes are primes whose difference is
6.
• The first few sexy primes pairs are {7,13},
{11,17}, {13,19}, and {17,23}
Wieferich Prime
• By Fermat's Little Theorem any prime p divides 2p-1-1. A
prime p is a Wieferich prime if p2 divides 2p-1-1. In 1909
Wieferich proved that if the first case of Fermat’s last
theorem is false for the exponent p, then p satisfies this
criterion. Since 1093 and 3511 are the only known such
primes (and they have been checked to at least
32,000,000,000,000), this is a strong statement!
• In 1910 Mirimanoff proved the analogous theorem for 3
but there is little glory in being second. Such numbers are
not called Mirimanoff primes.
Named and Notorious Primes
•
•
•
•
Early Primes
Named Primes
Hunting for Primes
Harnessing Primes
How Many Primes?
• Euclid proved there are infinitely many
primes
• N=(AxBxCx…P)+1, N>A,B,C…P. If N
prime, then it is larger than the others and
not included in the list. If N is composite,
then one of (A,B,C…) divides N, and
divides N-(AxBxC…) which is 1, which is
impossible. QED
Gauss and Legendre
• Gauss noticed the frequency of primes
approached N/log(N) but didn’t publish.
• Legendre noticed that the frequency of
primes approaches N/(log(N)-1.80366) and
published in 1808, finding that yet again,
Gauss had been there first.
• How Many Primes.xls
Prime Number Theorem
• Gauss mentioned in a letter, but did not
prove, that the number of primes less than x
can be approximated by:
• Proved independently by Jacques Hadamard
of France and Charles de la Vallee Poussin
of Belgium in 1896
Peter Gustav Lejeune-Direchlet
• Direchlet used Euler’s connection of primes
to the zeta function to prove Fermat’s
conjecture about infinitely many primes
modulo 1 to any base
• Zeta function - values can be calculated as
ζ(x) = 1/1x+1/2x+1/3x+…1/nx+…
Density Function
• Gauss introduced π(x)= # of primes less
than or equal to x
• Riemann showed that the zeta function can
also be written as a product over its zeroes
in the complex plane:
Riemann’s Hypothesis
• Fourier’s technique of adding waveforms to
model complex graphs, Cauchy’s weird
world of complex numbers, and Direchlet’s
fascination with Euler’s zeta function are
basic to Bernhard Riemann’s conjecture:
“The real part of any non-trivial zero of the
Riemann zeta function is 1⁄2.”
Prime Number Sieves
•
•
•
•
Eratothsenes Sieve
Excel Sieves
Quadratic Sieve
Number Field Sieve
Quadratic Sieve
• Data collection phase computes a
congruence of squares modulo the number
to be factored
• Data processing phase uses Gaussian
elimination to reduce a matrix of the
exponents of prime factors of the
remainders found in the data collection
phase.
Number Field Sieve
An extremely fast factorization method
developed by Pollard which was used to
factor the RSA-130 number. This
method is the most powerful known for
factoring general numbers.
Great International Prime Search
Great International Mersenne Prime Search
lets anyone with a computer be part of the
search for the next record-setting prime. In
November, 2001, Canadian student Michael
Cameron used his PC to prove the primality
of 213,466,917-1, the 39th Mersenne Prime.
Five more have been discovered since then.
Opportunity
• On September 4, 2006, Dr. Curtis Cooper
and Dr. Steven Boone's CMSU team
discovered the 44th known Mersenne prime,
232,582,657-1.
• Edson Smith using GIMPS found 243,112,609-1
(about 12.9 million digits, Aug 08), winning the
$100,000 prize from the Electronic Freedom
Foundation
Prime Generators
• There are several polynomial functions that
generate primes for a while before they start
yielding composite numbers.
• F(x) = x2 + x + 41 yields prime number for
x < 40.
Generating all primes
• No polynomial known which generates all
and only primes, but this generates only
primes and negative numbers:
•
F(a,b,…z) = (k + 2)(1 - (wz + h + j - q)2 - ((gk + 2g + k + 1)(h + j) + h z)2 - (2n + p + q + z - e)2 - (16(k + 1)3(k + 2)(n + 1)2 + 1 - f2)2 - (e3(e +
2)(a + 1)2 + 1 - o2)2 - ((a2 - 1)y2 + 1 - x2)2 - (16r2y4(a2 - 1) + 1 - u2)2 - (((a
+ u2(u2 - a))2 - 1)(n + 4dy)2 + 1 - (x + cu)2)2 - (n + l + v - y)2 - ((a2 - 1)l2 +
1 - m2)2 - (ai + k + 1 - l - i)2 - (p + l(a - n - 1) + b(2an + 2a - n2 - 2n - 2) m)2 - (q + y(a - p - 1) + s(2ap + 2a + p2 - 2p - 2) - x)2 - (z + pl(a - p) +
t(2ap - p2 - 1) - pm)2)
Elliptic Curve Factorization
Faster than the Pollard rho factorization
and Pollard p-1 factorization methods.
(Wolfram website)
Named and Notorious Primes
•
•
•
•
Early Primes
Named Primes
Hunting for Primes
Harnessing Primes
Prime Factorization
Every number can be expressed as a unique
product of prime numbers.
Example: 450 = 2*3*3*5*5
Greatest Common Factors
The Greatest Common Factor is the product
of the list of shared factors.
Example: 450 = 2*3*3*5*5
125 = 5*5*5
GCF(125,450) = 5*5
Least Common Multiple
The Least Common Multiple can be found
by writing the prime factorizations of both
numbers and crossing off one copy of the
set that forms the Greatest Common Factor.
Testing Processors
In 1995, Nicely discovered a flaw in the
Intel® PentiumTM microprocessor by
computing the reciprocals of 824633702441
and 824633702443, which should have
been accurate to 19 decimal places but were
incorrect from the tenth decimal place on.
Communication
In Carl Sagan’s novel Contact, aliens send a
series of prime numbers to show
intelligence behind radio transmissions
Quantum Physics
• The frequency of the zeroes of the Riemann
zeta function appears to match the energy
levels in the nucleus of a heavy atom when
it is being bombarded with low-energy
neutrons.
• Freeman Dyson noticed the similarity at a
chance meeting with mathematician Hugh
Montgomery.
Quantum Physics, II
• German Sierra and Paul Townsend will
publish a paper in Physical Review Letters
that suggests that an electron constrained to
move in two dimensions and constrained by
electric and magnetic fields have energy
levels that match the zeros of the zeta
function.
Winning Bets
• Don Zager, who argued against Riemann’s
Hypothesis, bet two bottles of wine that an
exception would be found in the first
300,000,000 roots.
• A Dutch team calculated an extra 100
million roots to help win the bet. Those
were the most expensive bottles of wine,
ever.
RSA Encryption
• Ron Rivest, Adi Shamir, and Len Adleman
harnessed Fermat’s Little Theorem to
enable secure web communications
• Fermat’s Little Theorem: if p is prime and a
is an integer not divisible by p, then
(ap-1)=1(mod p).
• Factoring large numbers is computationally
difficult
Named and Notorious Primes
Joyce Frost - [email protected]
Joe Frost - [email protected]