CSC 474/574 Dr. Peng Ning 1Computer ScienceCSC 474/574Information Systems SecurityTopic 2.3 Basic Number TheoryCSC 474/574 Dr. Peng Ning 2Computer ScienceBasic Number Theory• We are talking about integers!• Divisor– We say that b≠0 divides a if a = mb for some m,denoted b|a. b is a divisor of a.– If a|1, then a = 1 or –1.– If a|b and b|a, then a = b or –b.– Any b≠0 divides 0.– If b|g and b|h, then b|(mg+nh) for arbitrary integersm and n.CSC 474/574 Dr. Peng Ning 3Computer ScienceBasic Number Theory (Cont’d)• Prime numbers– An integer p > 1 is a prime number if its onlydivisors are 1, –1 , p, and –p.– Examples: 2, 3, 5, 7, 11, 13, 17, 19, 31,…• Any integer a > 1 can be factored in a uniqueway as– where each p1>p2>…>pt are prime numbers andwhere each ai>0.– Examples: 91=13¥7, 11011=13 ¥112 ¥7.tataapppa ...2121=CSC 474/574 Dr. Peng Ning 4Computer ScienceBasic Number Theory (Cont’d)• Another view of a|b:– Let P be the set of all prime numbers– Represent a as– Represent b as– a|b means that ai £bi..0 where, ≥P=Œ paPpapap.0 where, ≥P=Œ pbPpbpbpCSC 474/574 Dr. Peng Ning 5Computer ScienceBasic Number Theory (Cont’d)• Greatest common divisor: gcd(a,b)– gcd(a,b) =max{k | k|a and k|b}– Examples• gcd(6,15)=3.• gcd(60,24)=gcd(60,-24)=12.• gcd(a,0) = a.– gcd(a,b) can be easily derived if we can factor a and b.• Relatively Prime Numbers– Integers a and b are relatively prime if gcd(a,b) = 1.– Example: 8 and 15 are relatively prime.CSC 474/574 Dr. Peng Ning 6Computer ScienceModulo Operator• Given any positive integer n and any integer a, wehave a = qn+r, where 0£r<n and q=Îa/n˚.– We write a = r mod n.– The remainder r is often referred to as a residue.– Example:• 2 = 12 mod 5.• Two integer a and b are said to be congruent modulon if a mod n = b mod n.– We write a ≡ b mod n– Example:• 7 ≡ 12 mod 5.CSC 474/574 Dr. Peng Ning 7Computer ScienceModulo Operator (Cont’d)• Properties of modulo operator– a ≡ b mod n if n|(a – b)– (a mod n) = (b mod n) implies a ≡ b mod n.– a ≡ b mod n implies b ≡ a mod n.– a ≡ b mod n and b ≡ c mod n imply a ≡ c mod n.CSC 474/574 Dr. Peng Ning 8Computer ScienceModular Arithmetic• Observation:– The (mod n) operator maps all integers into the setof integers{0, 1, 2, …, (n-1)}.• Modular addition.– [(a mod n) + (b mod n)] mod n = (a+b) mod n• Modular subtraction.– [(a mod n) – (b mod n)] mod n = (a – b) mod n• Modular multiplication.– [(a mod n) ¥ (b mod n)] mod n = (a ¥ b) mod nCSC 474/574 Dr. Peng Ning 9Computer ScienceAn Exercise (n=5)• Addition • MultiplicationnnExponentiationExponentiationuu92921010 mod 5 = ____ mod 5 = ____4433221100443322110044332211004433221100CSC 474/574 Dr. Peng Ning 10Computer ScienceProperties of Modular Arithmetic• Zn={0, 1, …, (n-1)}• Commutative laws– (w + x) mod n = (x + w) mod n– (w ¥ x) mod n = (x ¥ w) mod n• Associative laws– [(w + x) + y] mod n = [w + (x + y)] mod n– [(w ¥ x) ¥ y] mod n = [w ¥ (x ¥ y)] mod n• Distributive law– [w ¥ (x + y)] mod n = [(w ¥ x)+(w ¥ y)] mod n• Identities– (0 + w) mod n = w mod n– (1 ¥ w) mod n = w mod n• Additive inverse (–w)– For each w ŒZn, there exists a z such that w + z=0 mod n.CSC 474/574 Dr. Peng Ning 11Computer ScienceAbout Multiplicative Inverse• Not always exist– Example: There doesn’t exist a z such that 6 ¥ z =1 mod 8.• An integer a ŒZn has a multiplicative inverseif gcd(a, n) = 1.• In particular, if n is a prime number, then allelements in Zn have multiplicative inverse.2244660022446600ResiduesResidues4242363630302424181812126600¥¥667766554433221100ZZ88CSC 474/574 Dr. Peng Ning 12Computer ScienceFermat’s Theorem• If p is prime and a is a positive integer notdivisible by p, then ap-1≡1 mod p.– Observation: {a mod p, 2a mod p, …, (p-1)a modp} = {1, 2, …, (p-1)}.– a ¥2a ¥.. ¥(p-1)a ≡[(a mod p) ¥(2a mod p) ¥…¥((p-1)a mod p)] mod p– (p-1)! ¥ap-1 ≡(p-1)! mod p– Thus, ap-1≡1 mod p.CSC 474/574 Dr. Peng Ning 13Computer ScienceTotient Function• Totient function ø(n): number of numbers lessthan n relatively prime to n– If n is prime, ø(n)=n-1– If n=p*q, and p, q are primes, ø(n)=(p-1)(q-1)• Examples:– ø(7)=____– ø(21)=____CSC 474/574 Dr. Peng Ning 14Computer ScienceEuler’s Theorem• For every a and n that are relatively prime, aø(n)≡1 mod n.– Proof leaves as an exercise.• Examples– a=3, n=10, ø(10)= ____ , 3ø(10) mod 10 = ____– a=2, n=11, ø(11)=____, 2ø(11) mod 11=____.CSC 474/574 Dr. Peng Ning 15Computer ScienceModular Exponentiation• xy mod n = xy mod ø(n) mod n• if y = 1 mod ø(n) then xy mod n = x mod n• Example:– 2100 mod 33 = ____CSC 474/574 Dr. Peng Ning 16Computer ScienceEuclid’s Algorithm• Observation– gcd(a, b) = gcd(b, a mod b)• Eulid (d, f), d > f > 0.1. X¨d; Y¨f2. If Y = 0 return X=gcd(d, f)3. R = X mod Y4. X ¨Y5. Y ¨R6. Goto 2CSC 474/574 Dr. Peng Ning 17Computer ScienceExtended Euclid Algorithm• Extended Euclid (d, f)1. (X1, X2, X3) ¨(1,0,f); (Y1, Y2, Y3) ¨(0,1,d)2. If Y3=0 return X3=gcd (d, f); no inverse3. If Y3=1 return Y3=gcd (d, f); Y2=d-1 mod f4. Q=ÎX3/Y3˚5. (T1, T2, T3) ¨(X1 - QY1, X2 - QY2, X3 - QY3)6. (X1, X2, X3) ¨(Y1, Y2, Y3)7. (Y1, Y2, Y3) ¨(T1, T2, T3)8. Goto 2• Observation– fX1 + dX2 = X3; fY1 + dY2 = Y3– If Y3 = 1, then fY1 + dY2 = 1– Y2 = d-1 mod fCSC 474/574 Dr. Peng Ning 18Computer ScienceThe Power of An Integer Modulo n• Consider the following expression• am≡1 mod n• If a and n are relatively prime, then there is at leastone integer m that satisfies the above equation.– That is, the Euler’s totient function f(n).• The least positive exponent m for which the aboveequation holds is referred to as:– The order of a (mod n)– The exponent to which a belongs (mod n)– The length of the period generated by a.CSC 474/574 Dr. Peng Ning 19Computer ScienceUnderstanding The Order of a (mod n)• Powers of Integers Modulo
View Full Document