YALE UNIVERSITY

DEPARTMENT OF COMPUTER SCIENCE

CPSC 467b: Cryptography and Computer Security | Handout #5 | |

Professor M. J. Fischer | February 9, 2010 | |

Number Theory Summary

- Integers
- Let Z denote the integers and Z+ the positive integers.
- Division
- For a Z and n Z+, there exist unique integers q,r such that a = nq + r and 0 ≤ r < n. We denote the quotient q by ⌊a∕n⌋ and the remainder r by a mod n. We say n divides a (written n∣a) if a mod n = 0. If n∣a, n is called a divisor of a. If also 1 < n < |a|, n is said to be a proper divisor of a.
- Greatest common divisor
- The greatest common divisor (gcd) of integers a,b (written gcd(a,b) or simply (a,b)) is the greatest integer d such that d∣a and d∣b. If gcd(a,b) = 1, then a and b are said to be relatively prime.
- Euclidean algorithm
- Computes gcd(a,b). Based on two facts: gcd(0,b) = b; gcd(a,b) = gcd(b,a - qb) for any q Z. For rapid convergence, take q = ⌊a∕b⌋, in which case a - qb = a mod b.
- Congruence
- For a,b Z and n Z+, we write a ≡ b (mod n) iff n∣(b-a). Note a ≡ b (mod n) iff (a mod n) = (b mod n).
- Modular arithmetic
- Fix n Z+. Let Z
_{n}= {0,1,…,n - 1} and let Z*_{n}= {a Z_{n}∣gcd(a,n) = 1}. For integers a,b, define a ⊕ b = (a + b) mod n and a ⊗ b = ab mod n. ⊕ and ⊗ are associative and commutative, and ⊗ distributes over ⊕. Moreover, mod n distributes over both + and ×, so for example, a + b × (c + d) mod n = (a mod n) + (b mod n) × ((c mod n) + (d mod n)) = a⊕b⊗ (c⊕d). Z_{n}is closed under ⊕ and ⊗, and Z*_{n}is closed under ⊗. - Primes and prime factorization
- A number p ≥ 2 is prime if it has no proper divisors. Any positive
number n can be written uniquely (up to the order of the factors) as a product of primes.
Equivalently, there exist unique integers k,p
_{1},…,p_{k},e_{1},…,e_{k}such that n = ∏_{i=1}^{k}p_{i}^{ei}, k ≥ 0, p_{1}< p_{2}< … < p_{k}are primes, and each e_{i}≥ 1. The product ∏_{i=1}^{k}p_{i}^{ei}is called the prime factorization of n. A positive number n is composite if (∑_{i=1}^{k}e_{i}) ≥ 2 in its prime factorization. By these definitions, n = 1 has prime factorization with k = 0, so 1 is neither prime nor composite. - Linear congruences
- Let a,b Z, n Z+. Let d = gcd(a,n). If d∣b, then there are d solutions x
in Z
_{n}to the congruence equation ax ≡ b (mod n). If d ~ ∣ b, then ax ≡ b (mod n) has no solution. - Extended Euclidean algorithm
- Finds one solution of ax ≡ b (mod n), or announces that there are none. Call a triple (g,u,v) valid if g = au + nv. Algorithm generates valid triples starting with (n,0,1) and (a,1,0). Goal is to find valid triple (g,u,v) such that g∣b. If found, then u(b∕g) solves ax ≡ b (mod n). If none exists, then no solution. Given valid (g,u,v), (g′,u′,v′), can generate new valid triple (g - qg′,u - qu′,v - qv′) for any q Z. For rapid convergence, choose q = ⌊g∕g′⌋, and retain always last two triples. Note: Sequence of generated g-values is exactly the same as the sequence of numbers generated by the Euclidean algorithm.
- Inverses
- Let n Z+, a Z. There exists unique b Z such that ab ≡ 1 (mod n) iff
gcd(a,n) = 1. Such a b, when it exists, is called an inverse of a modulo n. We write a
^{-1}for the unique inverse of a modulo n that is also in Z_{n}. Can find a^{-1}mod n efficiently by using Extended Euclidean algorithm to solve ax ≡ 1 (mod n). - Chinese remainder theorem
- Let n
_{1},…,n_{k}be pairwise relatively prime numbers in Z+, let a_{1},…,a_{k}be integers, and let n = ∏_{i}n_{i}. There exists a unique x Z_{n}such that x ≡ a_{i}(mod n_{i}) for all 1 ≤ i ≤ k. To compute x, let N_{i}= n∕n_{i}and compute M_{i}= N_{i}^{-1}mod n_{i}, 1 <= i <= k. Then x = (∑_{i=1}^{k}a_{i}M_{i}N_{i}) mod n. - Euler function
- Let ϕ(n) = |Z*
_{n}|. One can show that ϕ(n) = ∏_{i=1}^{k}(p_{i}- 1)p_{i}^{ei-1}, where ∏_{i=1}^{k}p_{i}^{ei}is the prime factorization of n. In particular, if p is prime, then ϕ(p) = p - 1, and if p,q are distinct primes, then ϕ(pq) = (p - 1)(q - 1). - Euler’s theorem
- Let n Z+, a Z*
_{n}. Then a^{ϕ(n)}≡ 1 (mod n). As a consequence, if r ≡ s (mod ϕ(n)) then a^{r}≡ a^{s}(mod n). - Order of an element
- Let n Z+, a Z*
_{n}. We define ord(a), the order of a modulo n, to be the smallest number k ≥ 1 such that a^{k}≡ 1 (mod n). Fact: ord(a)∣ϕ(n). - Primitive roots
- Let n Z+, a Z*
_{n}. a is a primitive root of n iff ord(a) = ϕ(n). For a primitive root a, it follows that Z*_{n}= {a mod n,a^{2}mod n,…,a^{ϕ(n)}mod n}. If n has a primitive root, then it has ϕ(ϕ(n)) primitive roots. Primitive roots exist for every prime p (and for some other numbers as well). a is a primitive root of p iff a^{(p-1)∕q}⁄≡ 1 (mod p) for every prime divisor q of p - 1. - Discrete log
- Let p be a prime, a a primitive root of p, b Z*
_{p}such that b ≡ a^{k}(mod p) for some k, 0 ≤ k ≤ p - 2. We say k is the discrete logarithm of b to the base a. - Quadratic residues
- Let a Z, n Z+. a is a quadratic residue modulo n if there exists y such
that a ≡ y
^{2}(mod n). a is sometimes called a square and y its square root. - Quadratic residues modulo a prime
- If p is an odd prime, then every quadratic residue in Z*
_{p}has exactly two square roots in Z*_{p}, and exactly half of the elements in Z*_{p}are quadratic residues. Let a Z*_{p}be a quadratic residue. Then a^{(p-1)∕2}≡ (y^{2})^{(p-1)∕2}≡ y^{p-1}≡ 1 (mod p), where y a square root of a modulo p. Let g be a primitive root modulo p. If a ≡ g^{k}(mod p), then a is a quadratic residue modulo p iff k is even, in which case its two square roots are g^{k∕2}mod p and -g^{k∕2}mod p. If p ≡ 3 (mod 4) and a Z*_{p}is a quadratic residue modulo p, then a^{(p+1)∕4}is a square root of a, since (a^{(p+1)∕4})^{2}≡ aa^{(p-1)∕2}≡ a (mod p). - Quadratic residues modulo products of two primes
- If n = pq for p,q distinct odd primes, then
every quadratic residue in Z*
_{n}has exactly four square roots in Z*_{n}, and exactly 1/4 of the elements in Z*_{n}are quadratic residues. An element a Z*_{n}is a quadratic residue modulo n iff it is a quadratic residue modulo p and modulo q. The four square roots of a can be found from its two square roots modulo p and its two square roots modulo q using the Chinese remainder theorem. - Legendre symbol
- Let a ≥ 0, p an odd prime. = 1 if a is a quadratic residue modulo p, -1
if a is a quadratic non-residue modulo p, and 0 if p∣a. Fact: = a
^{(p-1)∕2}. - Jacobi symbol
- Let a ≥ 0, n an odd positive number with prime factorization ∏
_{i=1}^{k}p_{i}^{ei}. We define = ∏_{i=1}^{k}^{ei}. (By convention, this product is 1 when k = 0, so = 1.) The Jacobi and Legendre symbols agree when n is an odd prime. If = -1 then a is definitely not a quadratic residue modulo n, but if = 1, a might or might not be a quadratic residue. - Computing the Jacobi symbol
- can be computed efficiently by a straightforward recursive
algorithm, based on the following identities: = 1; = 0 for n≠1; =
if a
_{1}≡ a_{2}(mod n); = 1 if n ≡ ±1 (mod 8); = -1 if n ≡ ±3 (mod 8); = ; = if a ≡ 1 (mod 4) or n ≡ 1 (mod 4); = - if a ≡ n ≡ 3 (mod 4). - Solovay-Strassen test for compositeness
- Let n Z+. If n is composite, then for roughly 1/2 of
the numbers a Z*
_{n}, ⁄≡ a^{(n-1)∕2}(mod n). If n is prime, then for every a Z*_{n}, ≡ a^{(n-1)∕2}(mod n). - Miller-Rabin test for compositeness
- Let n Z+ and write n-1 = 2
^{k}m, where m is odd. Choose 1 ≤ a ≤ n - 1. Compute b_{i}= a^{m2i }mod n for i = 0,1,…,k - 1. If n is composite, then for roughly 3∕4 of the possible values for a, b_{0}≠1 and b_{i}≠ - 1 for 0 ≤ i ≤ k - 1. If n is prime, then for every a, either b_{0}= 1 or b_{i}= -1 for some i, 0 ≤ i ≤ k - 1.

Michael J. Fischer

(Thanks to Miklós Csrös, Andrei Serjantov, and Jerry Moon for pointing out errors in previous
drafts.)

Last modified: October 26, 2000.