# Primality Testing Patrick Lee 12 July 2003 (updated

Primality Testing Patrick Lee 12 July 2003 (updated on 13 July 2003) Finding a Prime Number Finding a prime number is critical for publickey cryptosystems, such as RSA and DiffieHellman. Nave approach: Randomly pick a number n. Try if n is divided by 2, 3, 5, 7, ., p, where p is the largest prime number less than or equal to the square root of n. Computationally expensive. You need to pre-obtain all small prime numbers. 2 Introduction to Number Theory

Number theory: modular arithmetic on a finite set of integers Most of the randomized algorithms starts by choosing a random number from some domain and then works deterministically from there on. We hope that with high probability the chosen number has some desirable properties. Goal: Given a number n, the desired complexity is O(logn), i.e., polynomial in the length of n. 3 Computing GCD gcd(a, b): greatest common divisor of (a,b)

Euclids algorithm: a and b are co-prime iff gcd(a,b) = 1 Finding gcd(a,b) for a>b, gcd(a,b) = gcd(b, a mod b) Extended Euclids: Finding gcd d and numbers x and y such that d=ax+by 4 Groups Additive Group:

Zn = {0, 1, , n-1} forms a group under addition modulo n. Multiplicative Group: Zn* = {x | 1 <= x < n and gcd(x,n) = 1} forms a group under multiplication modulo n. For prime p, Zp* includes all elements [1,p-1]. E.g., Z6* = {1, 5} E.g., Z7* = {1, 2, 3, 4, 5, 6} 5 Chinese Remainder Theorem (CRT)

Given n1, n2,, nk are pairwise co-prime. There exists a unique r, r in [0, n = n1n2nk), satisfying r = ri mod ni for any sequence {r1,..,rk}, where ri in [0, ni). E.g., r = 2 (mod 3) r = 3 (mod 5) r = 2 (mod 7) We have r = 23, unique in [0,105). 6 Euler phi Function: phi(.) phi(n) = |Zn*| Theorem: if n= p1e1p2e2pkek, phi(n) = (p1-1)p1e1 - 1...(pk-1)pkek 1

e.g., phi(p) = p1 for prime p e.g., if n = pq, phi(n) = (p-1)(q-1) If we know phi(n), we can factorize n. Eulers Theorem: for all n and x in Zn* xphi(n) = 1 (mod n) For any prime p, xp-1 = 1 (mod p) for all x in [1, p-1]. (Fermats Little Theorem). If xn-1 <> 1, n is not prime (e.g., 45 mod 6 = 4). 7 Order and Generator ord(x): smallest t such that xt = 1 mod n

Generator: an element whose order = group size. E.g., in Z11*, ord(3) = 5, ord(2) = 10 E.g., 3 is the generator of Z7* Subgroup: generated from an element of order t < phi(n) {1,3,32=9,33=5,34=4} = {1,3,4,5,9} is a subgroup of Z11* A group is cyclic if it has a generator. For any prime p, the group Zp* is cyclic, i.e, every Zp* has a generator, say g. Zp* = {1, g, g2, g3, , gp-2}

8 Group Size Subgroup size divides group size (for all n) Group size = phi(n) We use an element of order t < phi(n) as the generator of the subgroup, (say 2 in Z7*). The subgroup spans t elements. For x in subgroup, we observe t has to divide phi(n) so that xtk = xphi(n) = 1, for some integer k. You can prove it by contradiction by assuming t does not divide phi(n). E.g., H = {1, 3, 4, 5, 9} is a subgroup of Z11*, |H| dividies | Z11*|. This proposition applies to all n (prime / composite).

9 Quadratic Residue y is a quadratic residue (mod n) if there exists x in Zn* such that x2 = y (mod n) i.e., y has a square root in Zn* Claim: For any prime p, every quadratic residue has exactly two square roots x, -x mod p. Proof: if x2 = u2 (mod p), then (x-u)(x+u) = 0 (mod p), so either p divides x-u (i.e., x=u), or p divides x+u (i.e., x=-u). It implies if x2 = 1 (mod p), x = 1 or -1. 10

Quadratic Residue (contd) Theorem: For any prime p, and g is generator, gk is a quadratic residue iff k is even. Given Zp* = {1, g, g2, g3, , gp-2} Even powers of g are quadratic residues Odd powers of g are not quadratic residues Legendre symbol: [a/p] = 1 if a is a quadratic residue mod p, and 1 if a is not a quadratic residue mod p. 11 Quadratic Residue (contd)

Theorem: For prime p and a in Zp*, [a/p] = a(p-1)/2 (mod p). Zp* is cyclic, a = gk for some k. If k is even, let k = 2m, a(p-1)/2 = g(p-1)m = 1. If k is odd, let k = 2m+1, a(p-1)/2 = g(p-1)/2 = -1. Reasons: This is a square root of 1. g(p-1)/2 <> 1 since ord(g) <> (p-1)/2. But 1 has two square roots. Thus, the only solution is -1. If n is prime, a(n-1)/2= 1 or -1. If we find a(n-1)/2 is not 1 and -1, n is composite. 12 Ideas of Primality Testing

Idea 1: If xn-1 mod n <> 1, n is definitely composite. If xn-1 mod n = 1, n is probably prime. Idea 2: If x(n-1)/2 mod n <> {1,-1}, n is definitely composite. If x(n-1)/2 mod n = {1,-1}, n is probably prime. 13 Simple Primality Testing Alg. Repeat k times:

Pick a in {2,...,n-1} at random. If gcd(a,n) != 1, then output COMPOSITE. [this is actually unnecessary but conceptually helps] If a(n-1)/2 is not congruent to +1 or -1 (mod n), then output COMPOSITE. Now, if we ever got a "-1" above output "PROBABLY PRIME" else output "PROBABLY COMPOSITE". 14 Error of the Simple Alg. The alg is BPP with error probability 1/2k. If n is prime, half of them makes a(n-1)/2 = 1. Prob. error in

each iteration is . If n is composite, error occurs if n is claimed to be PROBABLY PRIME. We use the key lemma. Key Lemma: Let n be an odd composite, not a prime power, and let t=(n-1)/2. If there exists a in Zn* such that at = -1 (mod n), then at most half of the x's in Zn* have xt = {-1,+1} (mod n). 15 Error of the Simple Alg. (contd) Let S = {x in Zn* | xt = 1 or -1} (let t = (n-1)/2). Wed like to show S is a proper subgroup of Zn*. S is a subgroup of Zn* since it's closed under multiplication (xt)(yt) = (xy)t.

Find b in Zn* but not in S. Let n = qr, where q and r are co-prime. Using the CRT notation, let b = (a,1), denoting b=a (mod q), b=1 (mod r). CRT assures the existence of b. Thus, bt = (at, 1t) = (-1, 1), implying b <> 1 and -1, since 1 = (1, 1) and -1 = (-1,-1). S is a proper subgroup. Since the subgroup size divides the group size, |S| <= |Zn*|. 16 Case of Prime-Power Composites

Key Lemma doesnt apply if n is a prime-power. However, it doesnt matter since it cannot pass the test of step (3), i.e., we are sure that a(n-1)/2 <> 1,-1 mod n for all a. Proof (assume all operations are mod n): Write n = pe, where p is prime. Consider an-1, which is equal to ape-1. Note that phi(n) = pe-1(p-1) = pe-pe-1, according to the theorem in slide 7. ape-1 = aphi(n)+pe-1-1 = ape-1-1 (by Eulers Theorem) Recursively, we get ape-1 = a-1. Since a<>1, a-1 <> 1. We have an-1 <> 1, and its square root is not 1 and -1.

Thus, if n is prime-power, it does not pass the test case in step (3). We can safely ignore the case of prime-powers in the Key Lemma. 17 Miller-Rabin Algorithm 1) pick a in {2,...,n-1} at random. 2) If an-1 != 1 (mod n), then output COMPOSITE 3) Let n-1 = 2r * B, where B is odd. 4) Compute aB, a2B, ..., an-1 (mod n). 5) 6) 7)

If we found a non {-1,+1} root of 1 in the above list, then output COMPOSITE. else output POSSIBLY PRIME. 18 Error of MR Algorithm It is RP. For prime n, the algorithm always returns prime. For non-Carmichael composite n, the algorithm returns prime with probability at most in each iteration (i.e., step 2 detects compositeness with probability at least ). Carmichael number: a composite n such that for all a in Zn*, an-1 = 1 mod n. (e.g., 561, 1729)

19 Error of MR Algorithm (Proof) Let Fn = {x in Zn* | xn-1 = 1 mod n}, the set of elements that do not violate Fermats theorem. Lemma: Let n be a composite non-Carmichael number. Then |Fn| <= |Zn*|. Clearly, Fn <> Zn* . Fn forms a group. There exists a such that an-1 <> 1 mod n. It is closed under multiplication (trivial proof!)

Fn is a proper subgroup of Zn*. |Fn| divides |Zn*|, and |Fn| is strictly less than |Zn*|. 20 Detecting Carmichael Numbers Computing aB, a2B, ..., a2rB (mod n), where B =(n-1)/2r, detects Carmichael numbers. Idea: a(n-1)/2 = {1,-1}, how about a(n-1)/4? If a(n-1)/4 = {1,-1}, how about a(n-1)/8? Prove by contradiction.

Assume n is Carmichael, for all a, aB = 1 mod n. Property: Carmichael number is the product of distinct prime. Thus, let n = p1p2..pk. Let g is a generator of Zp1*. Let a = (g, 1), i.e., a = g (mod p1), a = 1 (mod p2..pr), by CRT By assumption, aB = 1 (mod n). It implies gB = 1 (mod p1) (why?). Since g is the generator, B = p-1, which contradicts B is odd. Thus, for some a, aB <> 1. The probability is > . 21 How to Find a Prime Number? Algorithm: Randomly pick a number from [1,n-1]. Plug it into the primality testing algorithm. If fails, repeat the test with another number.

Are prime numbers rare? No. Prime number theorem: No. of prime numbers less than n ~ n/ln(n). 22 References R. Motwani and P. Raghavan, Randomized Algorithms, Ch. 14. CMU, Randomized algorithms, http://www-2.cs.cmu.edu/afs/cs/usr/avrim/w ww/Randalgs98/home.html

CLRS, Introduction to Algorithms, 2nd edition. Ch. 31. 23

## Recently Viewed Presentations

• Definition "A distressing persistent, subjective sense of physical, emotional and/or cognitive tiredness or exhaustion related to cancer or cancer treatment that is not proportional to recent activity and interferes with usual functioning."2012 National Comprehensive Cancer Network. Intensity is the key...
• Rhetorical Strategies vs Rhetorical Devices . A way or method of presenting a subject. Narration . Description. Process Analysis. Exemplification. Compare/ Contrast. Classification/Division. Definition. Cause/Effect. Rhetorical Appeals. Ethos, Pathos, Logos. A use of language that is intended to have an...
• HPC systems often derive their computational power from exploiting parallelism, meaning the ability to work on many computational tasks at the same time. HPC systems typically offer parallelism at a much larger scale, with hundreds, thousands, or (soon) even millions...
• Title: Chemistry of Life Author: Channell, Suzanne Last modified by: Channell, Suzanne Created Date: 9/2/2014 3:08:55 PM Document presentation format
• If either of the two students is caught cheating again, he will be suspended for three weeks. Practicing More Indefinite Pronouns Several of the audience members at the circus (was/were) accosted by the juggling platypus. Several of the audience members...
• Ask them all to make a fist - the heart is roughly the size of your fist! - as a full grown adult, your heart is roughly like the size of 2 of your fists. WHAT IS YOUR HEART? Your...
• Music 111: Music Appreciation with Dr. Jon Breman This course is an introduction to American, World and Western Classical music. The course introduces students to oral and written traditions and focuses on social milieu and the basic elements of music.
• Reserve irony for situations where there's a gap between reality and expectations, especially when such a gap is created for dramatic or humorous effect. ... Synonym: Consultation. Interview. Hearing. Readership. ELA. Grades 9-12. Unit 4. AUTHOR'S PURPOSE.