Discrete Mathematics for Computer Science
Explore prime factorization, primality testing, and the uniqueness of prime factorization in this educational presentation by Prof. Shachar Lovett, with examples and mathematical theorems discussed. Dive into the world of prime numbers and their significance in computer science.
Download Presentation
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
CSE 20: Discrete Mathematics for Computer Science Prof. Shachar Lovett
2 Today s Topics: 1. Prime factorization 2. Primality testing
3 1. Prime factorizations Primes are the atoms of integers
4 Primes Natural numbers: positive integers N={1,2,3, } Definition: ? ? is prime if the only natural numbers that divide it are 1,n By definition, 1 is not prime.
5 Primes Which of the following is prime? A. 1 B. 6 C. 7 D. 21
6 Prime factorization Basic theorem of number theory: any integer can be factored as a product of primes (we will prove this soon) Moreover, this factorization is unique Example: 36=2*2*3*3
7 Existence of prime factorization Theorem: For any integer ? 2 there exist primes ?1, ,?? such that ? = ?1?2 ??. Proof: strong induction Try and prove it by yourself first.
8 Existence of prime factorization Theorem: For any integer ? 2 there exist primes ?1, ,?? such that ? = ?1?2 ??. Proof: strong induction Base case: n=2. 2 is prime. We are done. Inductive case: let ? > 2. There are two cases: Case I: n is prime. We are done. Case II: n is not prime. So there is some 1 < ? < ? such that a|n. So ? = ? ? where 1<a,b<n. By strong induction, both a,b have a prime factorization: a=? 1? 2 ?? b=? 1? 2 ? ? So n=? 1? 2 ?? for some primes for some primes ? 1? 2 ? ? is a prime factorization of n.
9 How to find the prime factorization? What is the prime factorization of 100? A. 2*5 B. 2*2*5 C. 10*10 D. 2*2*5*5 E. Other
10 How to find the prime factorization? What is the prime factorization of 82768328638217?
11 How to find the prime factorization? What is the prime factorization of 82768328638217? Not so easy anymore The security of RSA (which for example, protects your bank accounts) is based on the assumption that it is hard to factor numbers We cannot prove it. In fact, maybe somebody knows how to factor numbers fast (lets wait for more Snowden revelations )
12 2. Primality testing
13 Primality testing If it s hard to factor numbers into primes, lets focus on an easier problem Test if a given integer is prime How can you do it? Try and come up with the best algorithm you can
14 Primality testing Algorithm 1: isPrime(n): 1. For i=2..n-1 If n MOD i=0: return False 2. Return True 1.1
15 Primality testing How many steps? Algorithm 1: A. ~n B. ~n2 C. ~log(n) D. Doesn t depend on n E. Other isPrime(n): 1. For i=2..n-1 If n MOD i=0: return False 2. Return True 1.1
16 Better primality testing? The primality testing algorithm uses n calls to the MOD function Even if we assume that MOD can be computed very efficiently (and it can), there are many call Observation: if n is not prime, then it has a factor of size ? Proof: If ? = ? ? then min ?,? ?. We can use it to design a faster algorithm.
17 Primality testing Algorithm 1: isPrime(n): 1. For i=2..n-1 If n MOD i=0: return False 2. Return True 1.1
18 Primality testing (II) Algorithm 2: isPrime(n): 1. For i=2.. ? If n MOD i=0: return False 2. Return True 1.1
19 Primality testing (II) How many steps? Algorithm 2: A. ~n B. ~n2 C. ~log(n) D. Doesn t depend on n E. Other isPrime(n): 1. For i=2.. ? If n MOD i=0: return False 2. Return True 1.1
20 An even faster algorithm? The prime numbers used in RSA are very big, with 100s of digits These algorithms will take forever There are much faster algorithms, which run in time ~log(n); they are randomized algorithm (e.g. Miller-Rabin)
21 Log vs poly time Assume n=10100 Then n or ? are very big (>>atoms in universe) But log(n)<1000 ! Algorithms running in log-time are very efficient!!!
