1、PART II Public-Key Encryption & Hash FunctionCHAPTER 8 Introduction to Number Theory 8.1 Prime Numbers 8.2 Fermats and Eulers Theorems 8.3 Testing for Primality 8.4 The Chinese Remainder Theorem 8.5 Discrete Logarithms 2048.1 Prime NumbersPrime numbers only have divisors of 1 and self they cannot be

2、 written as a product of other numbers eg. 2,3,5,7 are prime, 4,6,8,9,10 are notPrime numbers are central to number theoryPrime factorisation : Any integer a 1 can be factored in a unique way as: hard problem where p1 p2 pk are primes Another expression : P = set of all primes 11011 = 7 112 13 a7 =

3、1, a11 = 2, a13 = 12058.1 Prime NumbersMultiplication : k = a b Example : a = 12 = 22 3, b = 90 = 2 32 5 k = a b = 1080 = 23 33 5 k2(3) = a2(2)+b2(1); k3(3)= a3(1)+b3(2); k5(1) = a5(0)+b5(1)Given a and b, If a | b, then ap bp for all p Example : a = 12 = 22 3, b = 180 = 22 32 5 a2 = 2 = 2 =b2, a3 =

4、1 2 = b3, a5 = 0 0, q odd. Let a be any integer in the range 1 a 0, q odd, so that (n 1)=2kq(2) Select a random integer a, 1 a (n 1)(3) if aq mod n = 1 then return (“maybe prime);(4) for j = 0 to k 1 do if (a2jq mod n = n 1) then return( maybe prime )(5) return (composite)2158.3 Testing for Primalit

5、yRepeated Use of the Miller-Robin AlgorithmIf Miller-Rabin algorithm returns “composite” the number is definitely not prime, otherwise is a prime or a pseudo-primeProbability it detects a pseudo-prime is 1/4Hence, if repeat test with different random a, then chance n is prime after t tests is:Pr( n

6、is a prime after t tests ) = 1 4 teg. for t =10,2168.3 Testing for PrimalityA Deterministic Primality AlgorithmAKS (Agrawal, Kayal, Saxena, 2002) algorithm : relatively simple deterministic algorithm that efficiently determines whether a given large number is a prime.The AKS algorithm does not appea

7、r to be as efficient as the Miller-Rabin algorithm 2178.3 Testing for PrimalityDistribution of PrimesThe prime number theorem states that primes near n are spaced on the average one every (ln n) integers, i.e. the density of prime numbers among the integers in the neighborhood of n is around 1 in ln

8、 nLet (n) denote the number of primes p n. (n) n/(ln n 1 ), On average, one would have to test on the order of ln n integers before a prime is found. Because all even can be rejected, so in practice need only *ln(n) numbers of size n to locate a prime2188.4 Chinese Remainder TheoremUsed to speed up

9、modulo computations: A (mod M)Let M = m1 m2 mk where gcd(mi, mj) = 1Chinese Remainder theorem lets us work in each moduli mi separately: ai = A mod mi 1 i k where A ZM, ai ZmiSince computational cost is proportional to size, this is faster than working in the full modulus MTo compute A (mod M)first

10、compute all ai = A mod mi separatelydetermine constants ci below, where Mi = M/mi2198.5 Discrete LogarithmsThe Powers of an Integer, Modulo nFrom Eulers theorem, for gcd(a, n) = 1, a(n) mod n = 1 where (n) Eulers totient function: # of positive integers less than n and relatively prime to n.Consider

11、 am =1 (mod n), gcd(a, n) = 1must exist for m = (n), least m = order of aonce powers reach m, cycle will repeatIf smallest is m = (n), then a is called a primitive root of nIf p is prime, then successive powers of a generate the group mod p: Zp = a, a2, , ap1 For the prime p = 19, primitive roots =

12、2, 3,10, 13, 14, 152208.5 Discrete LogarithmsLogarithms for Modular ArithmeticThe discrete logarithm of a modulo p is to find an integer x such that y = gx (mod p); written as x = loggy (mod p)If g is a primitive root, then it always exists, otherwise it may not. x = log34 mod 13 has no answer; 3x =

13、 4 (mod 13) x = log23 mod 13 = 4 by trying successive powers The properties of logarithms : log x(1) = 0, log x(x) = 1 log x(yz) = log x(y) + log x(z) log x(y r) = r log x(y) 2218.5 Discrete LogarithmsCalculation of Discrete LogarithmConsider the equation y = gx mod p Given g, x, and p, it is a straightforward matter to calculate y; just exponentiation However, given g, y, and p, it is very difficult to calculate x. Hard problemThe fastest known algorithm for taking DL modu