Download presentation

Presentation is loading. Please wait.

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

© 2023 SlidePlayer.com Inc.

All rights reserved.