Report

CSE 20 DISCRETE MATH Prof. Shachar Lovett http://cseweb.ucsd.edu/classes/wi15/cse20-a/ Clicker frequency: CA Todays topics • Modular arithmetic • Section 6.2 in Jenkyns, Stephenson Recall: equivalence relations • Saw two equivalent definitions • xRy is an equivalence relation if… • Symmetric: ∀, , ⇔ • Reflexive: ∀, • Transitive: ∀, , , ∧ → • Equivalently: there is a partition of the universe to equivalence classes, and xRy iff x,y are in the same class • Can be phrased as: ∃, : → such that ⇔ = () Today: modular arithmetic • A very important (and very useful) example of an equivalence relation • Recall our example of {even,odd} classes: • ⇔ 2| − ⇔x,y are both even, or both odd • Modular arithmetic generalizes this from 2 to any divisor Modular arithmetic: definition • Fix ≥ 2 • Define a relation: integers x,y are equivalent modulo m, if = • Equivalently, | − • Defines a partition of Z to m equivalence classes = { ∈ : = } where ∈ {0,1, … , − 1} Modular arithmetic: examples • = { ∈ : = } • What is [0]2? A. All integers B. 0 C. Even numbers D. Odd numbers E. Other Modular arithmetic: examples • = { ∈ : = } • What is [1]2? A. All integers B. 1 C. Even numbers D. Odd numbers E. Other Modular arithmetic: examples • = { ∈ : = } • What is [0]3? A. All integers B. All integers divisible by 3 C. All integers whose value mod 3 is equal to 1 D. All integers whose value mod 3 is equal to 2 E. Other Modular arithmetic: examples • = { ∈ : = } • What is [1]3? A. All integers B. All integers divisible by 3 C. All integers whose value mod 3 is equal to 1 D. All integers whose value mod 3 is equal to 2 E. Other Modular arithmetic: examples • = { ∈ : = } • What is [4]3? A. All integers B. All integers divisible by 3 C. All integers whose value mod 3 is equal to 1 D. All integers whose value mod 3 is equal to 2 E. Other Modular arithmetic: notation • Notation: to say that ∈ , we typically write ≡ • More generally, for any two integers x,y we can write ≡ which means that x,y belong to the same equivalence class modulo m, which means | − . Modular addition and multiplication • Why is modular arithmetic so important? Because we can operate directly on the equivalence classes, adding and multiplying them (for a fixed modulus m) • Definition: for any fixed ≥ 2, + = + ∗ = ∗ And • Theorem: this is well defined • What does this even mean??? Modular addition • Theorem: + = + • Interpretation: if we take any ∈ , and any ∈ , then it is always true that + ∈ + • Equivalently: + = + Modular addition: proof • Theorem: + = + • Proof: we need to show ∀ ∈ , ∈ , + = + Let = + , = + and + = + , with , , ∈ {0, … , − 1}. Then: + = + + + = ++ + So + ∈ , and also a + ∈ . QED. Modular addition: examples • What is 0 2 + 1 2 ? A. B. C. D. E. 02 12 21 All integers Other Modular addition: examples • What is 4 7 + 5 7 ? A. B. C. D. E. 17 27 72 74 Other Modular addition: examples • What is 4 7 + 1 2 ? A. B. C. D. E. 57 5 14 72 1 14 Other Be careful! • We can only add + if = . Otherwise, this is not defined!!! • Also: in the special case of = 2, addition modulo 2 corresponds to XOR • 0 2+ 0 2= 0 2 • 0 2+ 1 2= 1 2 • 1 2+ 0 2= 1 2 • 1 2+ 1 2= 0 2 Modular multiplication • Theorem: ∗ = ∗ Modular multiplication: proof • Theorem: ∗ = ∗ • Proof: we need to show ∀ ∈ , ∈ , ∗ = ∗ Let = + , = + and ∗ = + , with , , ∈ {0, … , − 1}. Then: ∗ = + ∗ + = 2 + + + = 2 + + + + = + + + + So ∗ ∈ , and also a ∗ ∈ . QED. Applications of modular arithmetic • For a fixed ≥ 2, we can add, multiply and take modulo m, and the value (modulo m) will stay invariant • This is very useful; many algorithmic applications • Example 1: verifying calculations • Prove that 12294793 ∗ 2329373 ≠ 92739273 • Hint: use values modulo 10 Applications of modular arithmetic • Example 1: prove that 12294793 ∗ 2329373 ≠ 92739273 • Solution: compute values modulo 10 • 12294793 ≡ 3 10 • 2329373 ≡ 3 10 • 92739273 ≡ 3 10 • But 3 ∗ 3 ≡ 9 10 , so the equation cannot be correct Applications of modular arithmetic • Example 2: number theory • Theorem: there are no , ∈ such that 2 + 2 = 1234567 • Hint: use values modulo 4 Applications of modular arithmetic • Theorem: there are no , ∈ such that 2 + 2 = 1234567 • Hint: use values modulo 4 • Solution: for any ∈ , 2 ∈ 0 4 or 2 ∈ 1 4 . • There are 4 cases to check: • 0 4 ∗ 0 4 = 0 4; 1 4 ∗ 1 4 = 1 4; 2 4 ∗ 2 4 = 0 4; 3 4 ∗ 3 4 = 1 4; • So, 2 + 2 4 can either be 0 4 , 1 4 or 2 4 • But 1234567 ≡ 3 ( 4), so they cannot be equal! Applications of modular arithmetic • Cryptography • Your online transactions are encrypted, based on modular arithmetic • RSA public key crpytosystem: • Very large m, product of two large primes m=p*q • Message: ∈ {0,1, … , − 1} • Encryption: • Security is based on the assumption that factorization is hard