Explore modular arithmetic concepts such as addition, multiplication, negation, subtraction, and inverses. Learn how to compute and define these operations within a modulo setting. Understand the concept of modular inverse and why certain numbers may not have an inverse within a specific modulo. Delve into proofs and explanations to enhance your understanding of modular arithmetic.
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Clicker frequency: CA CSE 20 DISCRETE MATH Prof. Shachar Lovett http://cseweb.ucsd.edu/classes/wi15/cse20-a/
Todays topics More modular arithmetic Section 6.2 in Jenkyns, Stephenson
Modular negation Definition: the negation of an element a is an element b such that ? + ? = 0 What is the negation of 1 mod 5? A. 0 mod 5 B. 1 mod 5 C. 2 mod 5 D. 3 mod 5 E. 4 mod 5
Modular negation Definition: the negation of an element a is an element b such that ? + ? = 0 What is the negation of a mod m? A. a mod m B. a+1 mod m C. a-1 mod m D. m-a mod m E. Other
Modular subtraction We know how to do: Addition modulo m Negation modulo m How to do subtraction? To compute (a-b) mod m, we can A. Compute (-b) mod m, then add to a mod m B. Compute (-a) mod m, then add to b mod m C. Add a and b mod m, then negate D. Negate a, negate b, then add E. Other
Modular inverse Definition: the inverse of an element a is an element b such that ? ? = 1 Only define when ? 0 What is the inverse of 2 mod 5? A. 0 mod 5 B. 1 mod 5 C. 2 mod 5 D. 3 mod 5 E. 4 mod 5
Modular inverse Definition: the inverse of an element a is an element b such that ? ? = 1 Only define when ? 0 What is the inverse of 2 mod 6? A. 1 mod 6 B. 2 mod 6 C. 3 mod 6 D. 4 mod 6 E. 5 mod 6
Modular inverse Weird there seem to not be an inverse to 2 mod 6 Why? Claim: there is no b such that 2 ? 1 ??? 6 Proof: by contradiction. Assume that there is such a b. Then there exists ? ? such that 2 ? = 6? + 1 This however is impossible: the LHS is even, while the RHS is odd. So, we reached a contradiction, hence no such b can exist.
Modular inverse: existence So when is there an inverse to a modulo m? What do you think? A. Only if a=1 B. Only if m is prime C. Only if a,m don t have a common factor D. It is impossible to tell without trying all options E. Other
Modular inverse: existence Theorem: if a,m have no common factor, then there exists ? {1, ,? 1} such that ? ? 1 ??? ?. In particular, if m is prime, then there exists an inverse modulo m for all ? {1, ,? 1}. We will prove this special case. The proof can be extended to the general case.
Modular inverse: existence proof Theorem: if m is prime, ? 1, ,? 1 , then there exists ? {1, ,? 1} such that ? ? 1 ??? ?. Proof: define the set ? = 0, ,? 1 . Define a function ?:? ? by ? ? = ? ? ??? ?. We will show that f is one-to-one. This implies (since the domain,co-domain have the same size) that f is also onto. Hence, there must exist ? ? such that ? ? = 1, that is, ? ? = 1 ??? ?.
Modular inverse: existence proof (contd) m prime, ? {1, ,? 1}. Defined: ? = 0, ,? 1 , ?:? ? as ? ? = ? ? ??? ?. Need to show: f is one-to-one. Proof by contradiction: Assume not. Then there exist distinct ?,? ? such that ? ? = ?(?), which means ? ? = ? ? ??? ?, which means that ? ? such that ? ? ? = ? ? ? ? = ? ? Recall that m is prime. It divides the RHS. So, it must divide the LHS. As gcd(a,m)=1, we must have ?|? ?, but this means that ? ??? ? = ? ??? ?, which means x=y. A contradiction since x,y are distinct.
Modular arithmetic: summary so far Modulo m Always defined: addition, negation, subtraction, multiplication Sometimes defined: inverse (and also division) a/b mod m is defined whenever gcd(b,m)=1 Compute as a*(1/b mod m) mod m.
Modular power Want to compute ?? mod m ?,? 0, ? 2 Is it always defined (for any a,b,m)? A. Yes B. No
Modular power Want to compute ?? mod m ?,? 0, ? 2 How fast can we do it? Na ve way: multiply a with itself b times Works, but two problems What are the problems?
Recall: fast (non-modular) power Power(a,b) Inputs: ?,? 0 Output: ?? 1. ??? 1 2. While ? > 0: a. If b is odd: ??? ??? ? ? ? ??? 2 ? ? ? 3. Return ??? b. c.
Recall: fast (non-modular) power Power(a,b) Inputs: ?,? 0 Output: ?? 1. ??? 1 2. While ? > 0: a. If b is odd: ??? ??? ? ? ? ??? 2 ? ? ? 3. Return ??? Loop invariant: Res * ab b. c.
Recall: fast (non-modular) power Power(a,b) Inputs: ?,? 0 Output: ?? How to convert this to a fast modular power algorithm? 1. ??? 1 2. While ? > 0: a. If b is odd: ??? ??? ? ? ? ??? 2 ? ? ? 3. Return ??? b. c.
Fast modular power Power(a,b) Inputs: ?,? 0 Output: ?? 1. ??? 1 2. While ? > 0: a. If b is odd: ??? ??? ? ??? ? ? ? ??? 2 ? ? ? ??? ? 3. Return ??? b. c.
RSA* Secret: two very large primes p,q (say, 100 digits each) Public: product m=p*q Message: x {0, ,? 1} Encryption: ? = ?? ??? ? (? = 216+ 1 is commonly used, but theoretically can even use ? = 2) Decryption: ? = ?? ??? ?(such a d exists; we won t prove it here) Public key: m,e Secret key: d Anybody can encrypt To decrypt, need to know secret key However, to derive d from m,e, we need to know the factorization of m (eg p,q), which we think is a hard problem * I am cheating a little
Next class Order relations Section 6.3 in Jenkyns, Stephenson
