Loading...
Please wait, while we are loading the content...
Similar Documents
Advanced Algorithms 2.1 Primality Testing Cont'd. 2.1.1 the Miller-rabin Primality Test Cont'd. We Implement the Miller-rabin Test as Follows. Assume N 2 N . Miller-rabin(n; K) = Nd S Such That N ? 1 = 2
| Content Provider | Semantic Scholar |
|---|---|
| Abstract | s t, t odd repeat k times choose a 2 U Z N deene the sequence fu i g s i=0 by: u 0 := a t (mod N) if9i : 1 i s s.t. u i = 1 and u i?1 6 = 1 then return \not prime" return \probably prime" Claim 1 If N is prime, the algorithm decides correctly. If N is composite, the probability that the algorithm is incorrect is bounded above by 2 ?k. The rst part is obvious. If N is composite, we will show that for k = 1 the probability of returning \probably prime" is at most 1=2. Since the k a's are chosen randomly and independently, the claim follows. Before proving the second part, let us note that if we for instance choose k = 100, the algorithm answers correctly with an overwhelming probability: 1 ? 2 ?100. Also observe that the running time is O(kn 3), since for each of the k a's, we compute each of the at most n u i 's by a simple squaring. The idea behind the proof of claim 1 is to distinguish two special cases: 1. N is a prime power, N = p b , b 2 and 2-1 |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://www.nada.kth.se/theory/aalg/lecturenotes/lecture2/lecture2.ps |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
