Transcript Carmichael Numbers

Carmichael Numbers
and
Primality Tests
By
Sanjeev Rao
Outline


Introduction
Carmichael numbers




What is Carmichael number
Detecting a Carmichael number
Statistics and importance
Ancient Primality testing methods


Sieve of Eratosthenes
Chinese Primality Test
Introduction


Cryptographic algorithms uses big prime
numbers
Checking a big number is prime is not so
easy
Solution


Use probabilistic primality tests
Fermat Little Theorem:
If n is prime then
ap-1 ≡ 1 (mod p) for any integer a and p∤a.
Carmichael Numbers


Pseudoprime for every possible base b: that is, for
every b coprime to n
Passes Fermats little theorem test
Statistics




16 #s up to 100,000
43 #s up to 106
105,212 up to 1015 and 246,683 up to 1016
Example – 561, 1105, 1729, 2465 ….
Detecting Carmichael numbers
If n is a product of distinct prime numbers,
n = p1, p2, p3 ……. Ps , pi ≠ pj and
pi –1 | n-1 for every prime factor pi, i = 1……..
s,
then n is a Carmichael number.
Example: n = 561 = 3 x 11 x 17
2 | 560 , 10 | 560, 16 | 560
Importance


Encryption algorithms like RSA, ElGamal etc
must have large primes
For example, If we pick a Carmichael
number as a prime number p in RSA, we
can factor p and hence q and k
( k = (p-1) x (q-1) )
Primality testing


Process of proving a number is prime
Two of the oldest test methods


Sieve of Eratosthenes
Chinese Primality Test
Sieve of Eratosthenes




Greek mathematician
Found this method in 240 BC
One of the most efficient way to find all of the small
primes (say all those less than 10,000,000)
Sieve all primes less than given n
Sieve of Eratosthenes


contd…
Write down the numbers 1, 2, 3, ..., n. We will
eliminate composites by marking them. Initially
all numbers are unmarked
Mark the number 1 as special (it is neither prime
nor composite)
Sieve of Eratosthenes





contd…
Set k=1. Until k exceeds or equals the square root of n do this:
Find the first number in the list greater than k that has not been
identified as composite. (The very first number is 2.) Call it m.
Mark the numbers 2m, 3m, 4m, ... as composite. (Thus in the
first run we mark all even numbers greater than 2. In the
second run we mark all multiples of 3 greater than 3.)
m is a prime number. Put it on your list
Set k=m and repeat
Put the remaining unmarked numbers in the sequence on your
list of prime numbers
Example primes less than or equal to 30


2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
19 20 21 22 23 24 25 26 27 28 29 30
The first number 2 is prime, cross out its
multiples (color them red), so the red
numbers are not prime.
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
19 20 21 22 23 24 25 26 27 28 29 30
Example


contd…
Repeat this with the next number 3 and so
on…
Finally we have
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30

We are left with {2, 3, 5, 7, 11, 13, 17, 19,
23, 29} as primes less than 30
contd…


speed O(n(log n)log log n) bit operations
space O(n)
Disadvantages


Not efficient for big numbers
Needs lot of space to store big numbers
Possible solution

Large n use a segmented sieve

http://www.ieeta.pt/~tos/software/prime_sieve.html
Gives the algorithm and the runtime in seconds on a 900MHz Athlon
processor with 512Mbytes of memory running on GNU/Linux
A1, A2, A3 three different segmented sieve algorithms
Performance
n
12
14
16
18
A1
13.31
25.79
97.39
208.13
A2
14.08
20.62
26.26
32.36
A3
2.63
4.05
5.58
9.61
Chinese Primality Test



Found in approximately 500 B.C
Let n be an integer, n > 1.
If 2n is congruent to 2 (mod n) or 2n-1 ≡ 1 (mod n) ,
then n is either a prime or a base-2 pseudoprime.
A number that passes the Chinese Primality Test has
only a 0.002% chance of not being prime.
Contd …


In 1640, Fermat rediscovered what the ancient
Chinese had known nearly 2000 years before him.
He also examined the problem using bases other
than 2, improving on the accuracy of the Chinese
test.
References

Definitions
http://mathworld.wolfram.com/CarmichaelNumber.html

Sieve of Eratosthenes
http://primes.utm.edu/glossary/page.php?sort=SieveOfEratosthenes
http://ccins.camosun.bc.ca/~jbritton/jberatosthenes.htm
http://www.math.pku.edu.cn/stu/eresource/wsxy/sxrjjc/wk/Encyclopedia/math/e/e232.htm
http://www-2.cs.cmu.edu/afs/cs/project/pscico/doc/nesl/manual/node10.html

Segmented Sieve
http://www.ieeta.pt/~tos/software/prime_sieve.html
References
contd…
Chinese Primality testing
http://www-math.mit.edu/phase2/UJM/vol1/DORSEY-F.PDF

List of Carmichael Numbers –
http://www.kobepharma-u.ac.jp/~math/note/note02.txt

Questions
???