ModularArithmeticOperationscan do modular reduction at any point.a+bmodn=[amodn+bmodnlmodnE.g.97+23mod7=[97mod7+23mod7] mod7=[6+2] mod7= 1E.g.11-14mod8=-3mod8=5E.g.11x14mod8=3x6mod8=26
6 Modular Arithmetic Operations ◼ can do modular reduction at any point, ❑ a + b mod n = [a mod n + b mod n] mod n ❑ E.g. 97 + 23 mod 7 = [97 mod 7 + 23 mod 7] mod 7 = [6 + 2] mod 7 = 1 ❑ E.g. 11 – 14 mod 8 = -3 mod 8 = 5 ❑ E.g. 11 x 14 mod 8 = 3 x 6 mod 8 = 2
ModularArithmeticZ = {0, 1, ... , n-1]Ifa+b = a+c (mod n)thenb = c (mod n)ab = ac (mod n)but ifthen b = c (mod n) only if a is relatively prime to nnlab-ac n l a(b-c)口E.g. 7 x 11= 7x 5 (mod 6)11=5 (mod 6)口9 x 3= 9x 5 (mod 6)but 3 ! = 5 (mod 6)0
7 Modular Arithmetic ◼ Zn = {0, 1, . , n-1} ◼ If a+b ≡ a+c (mod n) then b ≡ c (mod n) ◼ but if ab ≡ ac (mod n) then b ≡ c (mod n) only if a is relatively prime to n ❑ n | ab – ac n | a(b – c) ❑ E.g. 7 x 11 7 x 5 (mod 6) 11 5 (mod 6) ❑ 9 x 3 9 x 5 (mod 6) but 3 ! 5 (mod 6)
Prime and Composite Numbers: An integer p is prime if its only divisors are ±1 and ±p only. Otherwise,it is a composite number.. E.g. 2,3,5,7 are prime; 4,6,8,9,10 are not: List of prime number less than 200:235 7 11131719 232931374143 4753596167717379838997101.103107109113127131137139149151.157163 167 173 179 181 191 193 197 199.PrimeFactorization:If aisacompositenumber,thena canbefactoredin a unique way asα= p1°- p22 .. p*+where p1 > P2 > ... > p+ are prime numbers and each α; is a naturalnumber (i.e. a positive nonzero integer).e.9. 12,250 = 72 .53 . 28
8 Prime and Composite Numbers • An integer p is prime if its only divisors are 1 and p only. • Otherwise, it is a composite number. • E.g. 2,3,5,7 are prime; 4,6,8,9,10 are not • List of prime number less than 200: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 • Prime Factorization: If a is a composite number, then a can be factored in a unique way as a = p1 1 p2 2 . pt t where p1 > p2 > . > pt are prime numbers and each i is a natural number (i.e. a positive nonzero integer). e.g. 12,250 = 72 5 3 2
Prime FactorizationIt is generally hard to do (prime)factorization whenthe number is largeE.g.factorize1.240702803121792.108930024809249102513.938740932174981739832107481234871432497619
9 Prime Factorization • It is generally hard to do (prime) factorization when the number is large • E.g. factorize 1. 24070280312179 2. 10893002480924910251 3. 93874093217498173983210748123487143249761
Greatest Common Divisor (GCD)GCD (a,b) of a and b is the largest number that divides both a and bE.g. GCD(60,24)= 12口IfGCD(a,b)=1,thenaandbaresaidtoberelativelyprimeE.g. GCD(8,15)= 1口8 and 15 are relatively prime (co-prime)口Question: Howto computegcd(a,b)?Naive method::factorizeaandbandcomputetheproductofall their common factors.e.g. 540 = 22× 33 × 5144 = 24 × 32gcd(540, 144) = 22 × 32 = 36Problem of this naive method:factorizationbecomes very difficultwhen integers become large.Better method: Euclidean Algorithm (a.k.a. Euclid's GCD algorithm)10
10 Greatest Common Divisor (GCD) ◼ GCD (a,b) of a and b is the largest number that divides both a and b ❑ E.g. GCD(60,24) = 12 ◼ If GCD(a, b) = 1, then a and b are said to be relatively prime ❑ E.g. GCD(8,15) = 1 ❑ 8 and 15 are relatively prime (co-prime) Question: How to compute gcd(a,b)? Naive method: factorize a and b and compute the product of all their common factors. e.g. 540 = 22 x 33 x 5 144 = 24 x 32 gcd(540, 144) = 22 x 32 = 36 Problem of this naive method: factorization becomes very difficult when integers become large. Better method: Euclidean Algorithm (a.k.a. Euclid’s GCD algorithm)