1
Prime and Relatively Prime Numbers
Divisors: We say that b 0 divides a if a = mb for some m, where a, b and m are integers. b divides a if there is no remainder on division. The notation b|a is commonly used to mean that b divides a. If b|a, we say that b is a divisor of a. YSL Information Security — Public-Key Cryptography

2
Prime and Relatively Prime Numbers (cont’d)
If a|1, then a = 1. If a|b and b|a, then a = b. Any b 0 divides 0. If b|g and b|h, then b|(mg + nh) for arbitrary integers m and n. YSL Information Security — Public-Key Cryptography

3
Prime and Relatively Prime Numbers (cont’d)
YSL Information Security — Public-Key Cryptography

4
Prime and Relatively Prime Numbers (cont’d)
Table 7.1 Primes under 2000 YSL Information Security — Public-Key Cryptography

5
Prime and Relatively Prime Numbers (cont’d)
The above statement is referred to as the prime number theorem, which was proven in 1896 by Hadaward and Poussin. YSL Information Security — Public-Key Cryptography

6
Prime and Relatively Prime Numbers (cont’d)
YSL Information Security — Public-Key Cryptography

7
Prime and Relatively Prime Numbers (cont’d)
Whether there exists a simple formula to generate prime numbers? An ancient Chinese mathematician conjectured that if n divides 2n – 2 then n is prime. For n = 3, 3 divides 6 and n is prime. However, For n = 341 = 11 31, n dives Mersenne suggested that if p is prime then Mp = 2p – 1 is prime. This type of primes are referred to as Mersenne primes. Unfortunately, for p = 11, M11 = = 2047 = 23 89. YSL Information Security — Public-Key Cryptography

8
Prime and Relatively Prime Numbers (cont’d)
Fermat conjectured that if Fn = 22n + 1, where n is a non-negative integer, then Fn is prime. When n is less than or equal to 4, F0 = 3, F1 = 5, F2 = 17, F3 = 257 and F4 = are all primes. However, F5 = = 641 is not a prime bumber. n2 – 79n is valid only for n < 80. There are an infinite number of primes of the form 4n + 1 or 4n + 3. There is no simple way so far to gererate prime numbers. YSL Information Security — Public-Key Cryptography

9
Prime and Relatively Prime Numbers (cont’d)
Factorization of an integer as a product of prime numbers Example: 91 = 7 13; = 7 112 13. Useful for checking divisibility and relative primality to be discussed later. Factorization is in gereral difficult. YSL Information Security — Public-Key Cryptography

10
Prime and Relatively Prime Numbers (cont’d)
Define notation gcd(a,b) to mean the greatest common divisor of a and b. The positive integer c is said to be the gcd of a and b if c|a and c|b any divisor of a and b is a dividor of c. Equivalently, gcd(a,b) = max[k, such that k|a and k|b] gcd(a,b) = gcd(-a,b) = gcd(a,-b) = gcd(-a,-b) =gcd(|a|,|b|) YSL Information Security — Public-Key Cryptography

11
Prime and Relatively Prime Numbers (cont’d)
gcd(a,0) = |a|. Factorization is one possible but in general inefficient way to calculate gcd. Whereas, Euclid‘s algorithm (to be discussed later) is more efficient. Relative primality the integers a and b are relatively prime if they have no prime factors in common or equivalently, their only common factor is 1 or equivalently, gcd(a,b) = 1 YSL Information Security — Public-Key Cryptography

12
Information Security — Public-Key Cryptography
Modular Arithmetic YSL Information Security — Public-Key Cryptography

13
Modular Arithmetic (cont’d)
Examples: a = 11; n = 7; 11 = 1 7 + 4; r = 4. a = -11; n = 7; -11 = (-2) 7 + 3; r = 3. If a is an integer and n is a positive integer, define a mod n to be the remainder when a is divided by n. Then, a = a/n n + (a mod n); Example: 11 mod 7 = 4; -11 mod 7 = 3. YSL Information Security — Public-Key Cryptography

14
Modular Arithmetic (cont’d)
YSL Information Security — Public-Key Cryptography

15
Modular Arithmetic (cont’d)
Properties of modular arithmetic operations Proof of Property 1: Define (a mod n) = ra and (b mod n) = rb. Then a = ra + jn and b = rb + kn for some integers j and k. Then, (a+b) mod n = (ra + jn + rb + kn) mod n = (ra + rb + (j + k)n) mod n = (ra + rb) mod n = [(a mod n) + (b mod n)] mod n YSL Information Security — Public-Key Cryptography

16
Modular Arithmetic (cont’d)
Examples for the above three properties YSL Information Security — Public-Key Cryptography

17
Modular Arithmetic (cont’d)
Properties of modular arithmetic Let Zn = {0,1,2,…,(n-1)} be the set of residues modulo n. YSL Information Security — Public-Key Cryptography

18
Modular Arithmetic (cont’d)
Properties of modular arithmetic (cont’d) if (a + b) (a + c) mod n, then b c mod n (due to the existence of an additive inverse) if (a b) (a c) mod n, then b c mod n (only if a is relatively prime to n; due to the possible absence of a multiplicative inverse) e.g. 6 3 = 18 2 mod 8 and 6 7 = 42 2 mod 8 but 3 7 mod 8 (6 is not relatively prime to 8) If n is prime then the property of multiplicative inverse holds (from a ring to a field). YSL Information Security — Public-Key Cryptography

19
Modular Arithmetic (cont’d)
Properties of modular arithmetic (cont’d) YSL Information Security — Public-Key Cryptography

20
Fermat’s and Euler’s Theorems
YSL Information Security — Public-Key Cryptography

21
Fermat’s and Euler’s Theorems (cont’d)
Fermat’s theorem (cont’d) alternative form if p is prime and a is any positive integer, then ap a mod p example: p = 5, a = 3, 35 = 243 3 mod 5 YSL Information Security — Public-Key Cryptography

22
Fermat’s and Euler’s Theorems (cont’d)
Euler’s totient function YSL Information Security — Public-Key Cryptography

23
Fermat’s and Euler’s Theorems (cont’d)
YSL Information Security — Public-Key Cryptography

24
Fermat’s and Euler’s Theorems (cont’d)
Euler’s totient function (cont’d) if n is the product of two primes p and q φ(n) = pq – [(q – 1)+(p –1) + 1] = pq – (p + q) + 1 = (p – 1) (q – 1) = φ (p) φ (q) YSL Information Security — Public-Key Cryptography

25
Fermat’s and Euler’s Theorems (cont’d)
YSL Information Security — Public-Key Cryptography

26
Fermat’s and Euler’s Theorems (cont’d)
Euler’s totient function (cont’d) YSL Information Security — Public-Key Cryptography

27
Information Security — Public-Key Cryptography
Testing for Primality If p is an odd prime, then the equation x2 1 (mod p) has only two solutions, 1 and -1. YSL Information Security — Public-Key Cryptography

28
Testing for Primality (cont’d)
YSL Information Security — Public-Key Cryptography

29
Testing for Primality (cont’d)
Probabilistic primality test YSL Information Security — Public-Key Cryptography

30
Information Security — Public-Key Cryptography
Euclid’s Algorithm YSL Information Security — Public-Key Cryptography

31
Euclid’s Algorithm (cont’d)
YSL Information Security — Public-Key Cryptography

32
Euclid’s Algorithm (cont’d)
YSL Information Security — Public-Key Cryptography

33
Euclid’s Algorithm (cont’d)
YSL Information Security — Public-Key Cryptography

34
Extended Euclid’s Algorithm
YSL Information Security — Public-Key Cryptography

35
Chinese Remainder Theorem
YSL Information Security — Public-Key Cryptography

36
Chinese Remainder Theorem (cont’d)
YSL Information Security — Public-Key Cryptography

37
Information Security — Public-Key Cryptography
Discrete Logarithms YSL Information Security — Public-Key Cryptography

38
Discrete Logarithms (cont’d)
YSL Information Security — Public-Key Cryptography

Similar presentations