YALE UNIVERSITY
DEPARTMENT OF COMPUTER SCIENCE

 CPSC 467b: Cryptography and Computer SecurityHandout #5
Professor M. J. Fischer   February 18, 2013



 

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∕nand the remainder r by a mod n. We say n divides a (written na) if a mod n = 0. If na, 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 da and db. 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 Zn = {0,1,,n - 1} and let Z*n = {a ∈ Zngcd(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)) = ab(cd). Zn 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,p1,,pk,e1,,ek such that n = i=1kpiei, k 0, p1 < p2 < < pk are primes, and each ei 1. The product i=1kpiei is called the prime factorization of n. A positive number n is composite if ( i=1kei) 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 db, then there are d solutions x in Zn 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 gb. 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 Zn. Can find a-1 mod n efficiently by using Extended Euclidean algorithm to solve ax 1 (mod n).
Euler function
Let ϕ(n) = |Z*n|. One can show that ϕ(n) = i=1k(pi - 1)piei-1, where i=1kpiei 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 ar as (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 ak 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,a2 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 ak (mod p) for some k, 0 k p - 2. We say k is the discrete logarithm of b to the base a.
Chinese remainder theorem
Let n1,,nk be pairwise relatively prime numbers in Z+, let a1,,ak be integers, and let n = ini. There exists a unique x ∈ Zn such that x ai (mod ni) for all 1 i k. To compute x, let Ni = n∕ni and compute Mi = Ni-1 mod ni, 1 <= i <= k. Then x = ( i=1kaiMiNi) mod n.
Quadratic residues
Let a ∈ Z, n ∈ Z+. a is a quadratic residue modulo n if there exists y such that a y2 (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 (y2)(p-1)2 yp-1 1 (mod p), where y a square root of a modulo p. Let g be a primitive root modulo p. If a gk (mod p), then a is a quadratic residue modulo p iff k is even, in which case its two square roots are gk∕2 mod p and -gk∕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. (  )
  ap = 1 if a is a quadratic residue modulo p, -1 if a is a quadratic non-residue modulo p, and 0 if pa. Fact: (a)
 p = a(p-1)2.
Jacobi symbol
Let a 0, n an odd positive number with prime factorization i=1kpiei. We define ( )
 an = i=1k(  )
  api-ei. (By convention, this product is 1 when k = 0, so ( )
 a1 = 1.) The Jacobi and Legendre symbols agree when n is an odd prime. If (a )
 n = -1 then a is definitely not a quadratic residue modulo n, but if (a)
 n = 1, a might or might not be a quadratic residue.
Computing the Jacobi symbol
(a-)
  n can be computed efficiently by a straightforward recursive algorithm, based on the following identities: ( )
 01 = 1; ( )
 0n = 0 for n1; (  )
 an1 = (  )
 an2 if a1 a2 (mod n); ( 2)
  n = 1 if n ≡ ±1 (mod 8); (2)
 n = -1 if n ≡ ±3 (mod 8); (  )
 2an = (  )
  2n( )
 an; (  )
 an = (  )
 na if a 1 (mod 4) or n 1 (mod 4); ( )
 an = -( )
 na 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 ⁄≡ a(n-1)2 (mod n). If n is prime, then for every a ∈ Z*n, (a)
 na(n-1)2 (mod n).
Miller-Rabin test for compositeness
Let n ∈ Z+ and write n-1 = 2km, where m is odd. Choose 1 a n - 1. Compute bi = am2i mod n for i = 0,1,,k - 1. If n is composite, then for roughly 34 of the possible values for a, b01 and bi - 1 for 0 i k - 1. If n is prime, then for every a, either b0 = 1 or bi = -1 for some i, 0 i k - 1.

Michael J. Fischer
(Thanks to Miklós Csu˝  rös, Andrei Serjantov, and Jerry Moon for pointing out errors in previous drafts.)
Last modified: February 16, 2012.