Primality, Factoring, RSA, Hensel's Lemma

Lecture 6 Primality, Factoring, RSA, Hensel's Lemma CRT and the number of solutions - we have a congruence ak xk + ak−1 xk−1 + · · · + a0 ≡ 0 (mod n), ai ∈ Z We want to know all solutions mod n, and in particular the number of solutions. Write n = pe11 pe22 . . . perr . Then solving the congruence mod m reduces to solving it mod pei i for all i. If x satisfies the congruence mod n then it is a solution of the congruence mod pei i for all i. Conversely if x1 is a solution mod pe11 and x2 is a solution mod pe22 , etc., then the CRT says that there exists a unique x mod n such that x ≡ xi mod pei i for all i. Now for this x, x ≡ xi mod pei i , so ak xk + ak−1 xk−1 + · · · + a0 ≡ ak xki + ak−1 xk−1 + · · · + a0 i ≡ 0 (mod pei i ) Therefore x is a solution mod n, so this process gives a bijection.       n o solutions solutions solutions × ... ↔ solutions e1 e2 er mod p1 mod p2 mod pr mod n In particular, the total number of solutions mod n is r Y # of solutions mod pei i i=1 Primality Testing: Given n, we want to determine if n is prime or composite. Input n has log n digits. We call an algorithm efficient if it’s polynomial in input - in this case, poly(log √ n) steps. Obvious √ algorithm is to divide by every prime starting from 2 to b nc, which is O( n) steps, or exp( 12 log n). Test using Fermat’s Little Theorem - if n is prime and n - a, then an−1 ≡ 1 mod n. 1. Pick an integer a ∈ {2 . . . n − 1}. 2. Compute (a, n): if it is > 1, then n is composite. 3. Otherwise compute an−1 : if 6≡ 1 mod a then done, n is composite. If ≡ 1 mod n, then is inconclusive. Could try another random a. There are composite numbers that satisfy an−1 ≡ 1 mod n for all (a, n) = 1 (eg., 561) called Carmichael numbers. 1 Refinement: if an−1 ≡ 1 mod n, compute a prime, must equal ±1 mod n. If a n−1 2 n−1 2 (since n − 1 is even). If n is 6 ±1 mod n, then n is composite ≡ ≡ −1 mod n, then inconclusive, go to another a ≡1 mod n and 4|n − 1, then repeat with a n−1 4 If n passes all these tests for a given a, n is a strong pseudoprime to base a. If n is prime, it’s going to pass all these tests. If n is composite, it’s pseudoprime to base a for at most 34 of all possible a (usually much smaller). So if we pick a random a mod n then n will pass the test with probability at most 43 . If it passes, then pick another random a. The probability of n passing k tests will be at most ( 34 )k , which decreases exponentially with k. And so if you do c log n trials, the at most probability goes like n1∗ . So if n passes c log n trials (for some large enough c ≈ 100), then probability that n is prime is very close to 1. This is poly(log) steps, but we want a deterministic algorithm. Solved in 2002 by AKS (Agrawal, Kayal, Saxena). The main idea is that n > 2 is prime if and only if (x − a)n ≡ xn − a (mod n) as polynomials Check different values of a, but there are n possible choices of a and expansion is slow. Way to avoid is with CRT by looking at both sides mod n and modulo a small degree polynomial. Factorization If n is composite, how do we √ factor in poly(log n) time. The obvious way is to divide by all, which is O( n). Pollard Rho Let f (x) = x2 + 1. x0 = 1, x1 = f (x0 ) mod n, xn = f (xn−1 ) mod n gives the sequence x0 , x1 , . . . xi . Heuristic: if n = pm with small p then this sequence will start repeating mod p earlier than mod n. So if xj ≡ xi mod p but not mod n, then (xi − xj , n) will give a factor of n. In practice only need to compute xk and x2k , x2k and x4k , etc., and check gcd. Heuristic: if p is smallest prime factor of n, we expect to get a factor of n using √ this algorithm in about p steps. √ Elliptic curve based factoring gives exp(c log n log log n). Number field sieve 1 gives exp(c(log n(log log n)2 ) 3 ). We still don’t have an efficient algorithm for factoring, a fact that much of modern cryptography is based on. Cryptography - RSA Alice and Bob (A and B) want to pass messages, and Carol is eavesdropper. A can send a message to B, converted into bits - equivalent to sending an integer m. Wants to encrypt the number so C can’t understand it. 2 Obvious method is to use a shared key model, where A and B have some shared key. With a message m, A can send m + k, or m ⊕ k (where ⊕ is the bitwise exclusive OR). B can decrypt the message by subtracting k: (m + k) − k = m, (m ⊕ k) ⊕ k = m. This is not so good if we want to send multiple messages - if C sees m1 + k and m2 + k, then C can figure out m1 − m2 , which gives her some information about m1 and m2 , which is bad. This is also not efficient (number of keys needed grows quadratically as number of members to pass messages between increases). Instead, use public key cryptography. One model is RSA (Rivest, Shamir, Adleman). The idea is that B generates two large primes p and q of about equal size. Set N = pq. φ(N ) = φ(p)φ(q) = (p − 1)(q − 1) Then B chooses e coprime to φ(N ) and computes f = e−1 mod φ(N ). B publishes N and e as his public key. If A wants to send message m, assuming that 0 < m < N (if not, then we break into chunks), and (m, N ) = 1. A then computes me mod N and sends it to B, who decrypts it by computing (me )f mod N . The idea is that f = e−1 f e ≡ 1 (mod φ(N )) = 1 + kφ(N ) mef = m1+kφ(N ) = m(mφ(N ) )k ≡ m1k (mod N ) ≡ m (mod N ) f is secret, so C has no way to compute m from me - this relies on the hardness of factoring. Hensel’s Lemma - this is a way to solve congruences mod pe if we know solutions mod p (analog to Newton’s Method for finding roots of polynomials). Theorem 26 (Hensel’s Lemma). Suppose that f (x) ∈ Z[x], f (a) ≡ 0 mod pj , and f 0 (a) 6≡ 0 mod p. Then there’s a unique t mod p such that f (a + tpj ) ≡ 0 mod pj+1 . That is, there’s a unique solution b mod pj+1 which is congruent to a mod pj , (ie., b reduces to a mod pj , a lifts to b mod pj+1 ). Proof. We’re looking for solutions b = a + tpj where t ∈ {0, 1, . . . p − 1} to the congruence mod pj+1 . Want to see if one of these t works. Use Taylor expansion around a: f (a + tpj ) = f (a) + tpj f 0 (a) + (tpj )2 00 (tpj )n (n) f (a) + · · · + f (a) 2! n! 3 Lemma 27. f (a + tpj ) ≡ f (a) + tpj f 0 (a) (n) mod pj+1 if j ≥ 1 Proof. fn! is an integer if f is a polynomial with integer coefficients, and so follows after we see that pnj ≡ 0 mod pj+1 .  (Cont’d next section) 4