Cryptology Tutorial: Understanding Primes and Generating Large Numbers

Introduction to Cryptology Tutorial-3 Mathematical Background: Primes and (GF) 22.03.2023, v40 Page : 1

Summary: Primality check and generating primes Fermat s Theorem to check primality: If for any b, where 1 < b < p the following holds bp-1 1 then p is a pseudo prime to the base b mod p, Find Provably-Primes Pocklington s Theorem (1916) Pocklington Let n = 1 + F R and let F = q1... qtbe the distinct prime factors of F. If there exists a number a such that all the following three conditions hold, 1. an-1 1 (mod n) 2. for all qis where 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 s Theorem is (1 1/qi) Page : 2

To generate large prime numbers; start with a small list, then use Pocklington s theorem to get larger and larger primes List of Primes up to 4483 Page : 3

Problem 3-1: Primality test Prove that the following numbers 17, 13, 31 are pseudoprimes to the bases 2 and 3. Fermat s Theorem to check primality: If for any b, where 1 < b < p the following holds bp-1 1 then p is a pseudoprime to the base b mod p, Solution 3-1: 217-1 1 213-1 1 231-1 1 mod 17 mod 13 mod 31 317-1 1 313-1 1 331-1 1 mod 17 mod 13 mod 31 Page : 4

Problem 3-2: Generating definitely prime numbers To set up a cryptographic system the we used the following known prime numbers for generating larger primes: 2, 3, 7, 11, 13 1. Using Pocklington s Theorem the following number was constructed n = 4*7+1 = 29. Check if n = 29 is for sure a prime. 2. Generate GF(29) and find 3 primitive elements. Solution 3-2: 1. n = 4*(7) + 1 = 29, F = 7 and R = 4 29 is prime if the following conditions all hold : 1. gcd (2(29-1)/ 7 1 , 29) = gcd (24 1 , 29) = gcd (15,29) = 1 is true 2. 229-1= 1 mod 29 or in Z29 3. F = 7 > 29 => 7 > 5.-- is true As all conditions hold, 29 is for sure a prime 2. The possible multiplicative orders in GF(29) are the divisors of (29) = 29 1 = 28, namely 1, 2, 4, 7, 14 , 28 Number of the primitive elements with the highest order order 28 is (28) = (22 x 7)= 28 (1-1/2) (1-1/7) = 12 Order of 2: 21= 2 1, 22= 4 1, 24= 16 1 , 27= 2*64= 2 * -6 = -12 1, 214= (-12)2 = 144 = -1 1 => order of 2 is 28 => 2 is a primitive element. 23 = 8 and 25 = 3 are also primitive as gcd(28,3) = 1 and gcd(28,5) = 1. (Notice: The primitive elements are all 2ifor which gcd(28,i) = 1 namely: 21, 23, 25, 29, 211, 213 ,215, 217, 219, 223,225, 227) is true Page : 5

Problem 3-3: Generating provably prime numbers (online exercise) To set up a cryptographic system the we used the following known prime numbers for generating larger primes: 2, 3, 7, 11, 13, 17 1. Using Pocklington s Theorem the following number was constructed n = 2x (3x17)+1 = 103. Check if n = 103 is for sure a prime. 2. Generate GF(103) and find 5 primitive elements Solution 3-3: 1. n = 2 * (3.17) + 1 = 103 , F = 3.17=51 and R = 2 (1) 103 is prime if the following conditions all hold : select a=2 for Pocklington s theorem. 1. gcd (2(103-1)/3 1 , 103) = gcd (234 1 , 103) = 1 is true 2. gcd (2(103-1)/17 1 , 103) = gcd (26 1 , 103) = 1 is true 3. F = 7 > 103 => 51 > 10.-- is true, As all conditions hold,103 is for sure a prime The possible multiplicative orders in GF(103) are the divisors of (103) = 103 1 = 102= 1x2x3x17 (from (1) ) namely 1, 2, 3, 6,17,34,51,102 Number of the primitive elements with the highest order 102 is (102) = (2x3x17)= (2-1)(3-1(17-1)= 32 Order of 2: 21= 2 1, 22= 4 1, 23= 8 1 , 26= 64 1, 217= 56 1 , 234= 46 1 , 251= 1, => order of 2 is 51 Order of 5: 51= 5 1, 52= 25 1, 53= 22 1 , 56= 72 1, 517= 57 1 , 234= 56 1 , 551= 102 1 => order of 5 is 102 5 is a primitive element (Notice: The primitive elements are all 5ifor which gcd(102,i) = 1 namely: 51, 55, 57, 511, 513 .. = 5, 35, 51, 48, 67 . 2. Page : 6