| Tired of seeing ads? Click here to upgrade to Elite Membership! |
Mathematics Forum
|
| Author | Message / Information |
| nochipfritz Quote | Reply | This message was updated on 7/19/2006 5:31:54 AM by nochipfritz | Problems with Miller Rabin Test posted on: 7/19/2006 5:17:07 AM Hello, I'm a italian student and I search a correctness proof of Miller rabin test. I read from a paper : A primality test is a prediacate T(n,a) where 1<=a <n with the following properties 1) the number n is composite iff T(n,a) holds for some a 2) T(n,a) can be efficently computed 3) when n is composite, let L(n) be the set of integers for which T(n,a) does not hold, then #L(n) / n-1 <= 1/2 Now, if I have the miller-rabin's predicate MR(n,a) defined as: MR(n,a) = {a^m<>1 mod n and a^{m*2^v}<>1 mod n for any 0<=v< k } with n-1 = m * 2^k where m is odd How show that MR(n,a) holds necessity of first property ? Excuse me for my english :-) Thanks. |
|
|
| Tired of seeing ads? Click here to upgrade to Elite Membership! |
ChatArea.com Help & News Forums | Terms of Use | Contact ChatArea.com | Advertising
Powered By ChatArea.com - Get your free Society today! © Copyright 2003 Wewp!