Transcript a 1
Network Security Design Fundamentals ET-IDA-082 Lecture-4 Mathematical Background: Prime Numbers 13.04.2016, v24 Prof. W. Adi Technical University of Braunschweig IDA: Institute of Computer and Network Engineering Page : 1 W. Adi 2011 Mathematical Background In Discrete Mathematics, number theory Outlines • Euclidean Algorithm, Remainder • Greatest Common Divisor (gcd) part 1 • Group Theory, Rings, Finite Fields • Element’s Order, Euler Theorem part 2 • Prime Numbers • Prime Number Generation part 3 • Extension Fields part 4 Technical University of Braunschweig IDA: Institute of Computer and Network Engineering Page : 2 W. Adi 2011 Prime Numbers Primes are necessary to generate a GF Prime numbers like : 2, 3, 5, 7, …..13 ,17 ,19 ….. How many primes do exist less which are than n? There is an simplified approximate number of (n) primes where: lim (Tchebycheff Theorem) n (n) n 1 or lim n (n) n ln( n) ln( n ) Example: For 1 r 10100 = n Pr(r=prime) = ( n) n 1 ln( n) 1 230 Technical University of Braunschweig IDA: Institute of Computer and Network Engineering ( n 10100 ) Page : 3 W. Adi 2011 Sample prime numbers List of Primes up to 4483 Technical University of Braunschweig IDA: Institute of Computer and Network Engineering Page : 4 W. Adi 2011 How to Find Probably-Primes ? Based on: Fermat´s Theorem • If p is a prime number where 1 < b < p then • Primality test: b p-1 = 1 (mod p) If an integer m verifies Fermat theorem for some b, That is; bm-1 = 1 (mod m) then m is called a pseudoprime to the base b. The probability that m is a prime is > 2-1 • Miller test is widely used as primality test based on Fermat theorem Technical University of Braunschweig IDA: Institute of Computer and Network Engineering Page : 5 W. Adi 2011 How to Find Probable Primes? Use Miller Test m is odd Widespread primality test algorithm Serch for s and Q such that m-1= 2s Q, Q is odd Compute yes no yes no yes m is a strong pseudoprime for the base b no Miller test based on Fermat theorem for t independent random choice of b has the probability that m is not a prime roughly < 4-t m is not a prime Technical University of Braunschweig IDA: Institute of Computer and Network Engineering Page : 6 W. Adi 2011 How to Find Provably-Primes ? Pocklington´s Theorem (1916) Pocklington Let n = 1 + F R and let F = q1 ... qt be the distinct prime factors of F. If there exists a number a such that 1. an-1 ≡ 1 (mod n) 2. for all i = 1 .. t, gcd (a(n-1)/qi - 1, n) = 1, 3. if F > n, then n is prime. If n is prime the probability that a randomly selected a which satisfies Pocklington is (1 – 1/qi) Example: n = 2 ( 3. 11 ) + 1 = 67, F = 3 x 11 and R=2. Is 67 a prime? Proof: 1. gcd ( 2 (67-1)/ 3 –1 , 67 ) = gcd ( 222 –1 , 67 ) = 1 is true (selecting a=2) gcd ( 2 (67-1)/ 11 –1, 67 ) = gcd ( 26 –1 , 67 ) = 1 is true 2. 267-1 = 1 mod 67 ( or in Z67 ) is true 3. F = 3 x 11 > 67 => 33 > 8.18 is true => 67 is prime By selecting R=3 => n = 3 (3x11) +1 = 100. Is 100 a prime?. Check condition 2: 2100-1 = 299 =88 1 in (mod 100) (condition 2 is not true) => 100 is not a prime ! Technical University of Braunschweig IDA: Institute of Computer and Network Engineering Page : 7 W. Adi 2011 Example: Prove that 67 is a prime , examine GF(67) Algebra Some facts in GF(67) Number of invertible elements in GF(67) is Euler function (67) = (67-1)=66 = 2.3.11 The possible multiplicative orders in GF(67) are the divisors of 66 namely 1, 2, 3, 6,11,22,33,66 Number of elements with order 1 is (1) = 1 Number of elements with order 33 is (33) = (3x11)=(3-1) (11-1)= 20 Number of elements with order 66 is (66) = (2x3x11)=(2-1)(3-1)(11-1)= 20 order of 11: 111 = 111, 112 = -131, 113 =-91, 115=501, 116=14, 1111=30, 1122=29 1, 1133=29x11=-1 1 => order of 11 is 66. Now we know that the order of 11 is 66 , thus Ord (11i ) = 66 / gcd (66,i). by selecting i=2 => order [ 112]=54 = 66/2=33. by selecting i=5 => order [115=50]= 66/1=66. by selecting i=6 => order [116 ]= 66/6=11. 1. 2. 3. 4. Mult. Inv of 31 GF( 67) =13 n1 n2 67 31 a1-qa2 b1-qb2 a1 b1 a2 b2 q r 1 0 0 1 2 5 1 31 5 0 1 5 1 1 -2 --- 0-2x1 -2 1-6x-2 13 Technical University of Braunschweig IDA: Institute of Computer and Network Engineering computation 67/31 =2 + 5/67 6 1 31/5= 6 +1/5 5 0 5/1=5+ 0/1 Page : 8 W. Adi 2011