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 arbitraryintegers m 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.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.CSC 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 r = a 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 • MultiplicationExponentiation9210 mod 5 = ____43210432104321043210CSC 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.24602460Residues42363024181260×676543210Z8CSC 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 integers lessthan n and 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 φ(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 19118118118118118118118118118117411166759117411166759112111878112111878112111878111711171117111711171117156111797164156111797164110512631115171891471316842111111111111111111a18a17a16a15a14a13a12a11a10a9a8a7a6a5a4a3a2aCSC 474/574 Dr. Peng Ning 20Computer ScienceObservations in The Previous Table• All sequences end in 1.• The length of a sequence divides φ(19) = 18.– Lengths: 1, 2, 3, 6, 9, 18.• Some of the sequences are of length 18.– The base integer a generates (via powers) allnonzero integers modulo 19.CSC 474/574 Dr. Peng Ning 21Computer