June 24th, 2013, 10:28 AM  #1 
Member Joined: May 2013 Posts: 31 Thanks: 1  prime check problem
hey guys, I'm having a hard time finding the error in my logic for the following implementation of the Rabin Miller prime check algorithm. Code: import random def mod(a,b): k = 0 while b << 1 < a: b = b << 1 k += 1 while k > 0: if a > b: a = b b = b >> 1 k = 1 if a > b: a = b return a def probprime(prime,witness): s = 0 d = prime1 while d&1 ==0: d = d >> 1 s += 1 v = 1 while d > 0: if d&1 == 1: v = v*witness d = 1 else: d = d >> 1 v = mod(v*v,prime) print v if v > prime: v = mod(v,prime) if v == 1 or v == prime1: return "probably prime",witness else: r = 1 while r < s: v = mod(v*v,prime) if v == prime1: return "probably prime",witness break else: r += 1 return "composite",witness probprime(213067,17) so, something must be wrong in my interpretation of the algorithm, but i can't for the life of me figure out what. 
June 24th, 2013, 12:34 PM  #2 
Member Joined: May 2013 Posts: 31 Thanks: 1  Re: prime check problem Code: def mod(a,b): k = 0 while b << 1 < a: b = b << 1 k += 1 while k > 0: if a > b: a = b b = b >> 1 k = 1 if a > b: a = b return a def probprime(prime,witness): s = 0 d = prime1 while d&1 ==0: d = d >> 1 s += 1 print d v = 1 while d > 0: if d&1 == 1: v = v*witness d = 1 else: d = d >> 1 v = mod(v*v,prime) print v if v > prime: v = mod(v,prime) if v == 1 or v == prime1: return "probably prime",witness else: r = 1 while r < s: v = mod(v*v,prime) if v == prime1: return "probably prime",witness break else: r += 1 return "composite",witness probprime(213067,17) 
June 24th, 2013, 12:37 PM  #3 
Member Joined: May 2013 Posts: 31 Thanks: 1  Re: prime check problem
bah i did post the whole code just didn't notice the scroll bar! duh. mod is taking the modulus a mod b. the small snippet you're referring to is doubling the value of b until just before doubling puts it larger than a. 
June 24th, 2013, 12:49 PM  #4 
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 933 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  Re: prime check problem
What language is this in? Don't you have a mod function already? One possible problem is that you don't reduce v at each step, so it might be overflowing. 
July 11th, 2013, 06:39 AM  #5 
Newbie Joined: Jul 2013 Posts: 2 Thanks: 0  Re: prime check problem
Hi phillip1882, Your computation of a=witness to the power d mod prime is wrong. For example, with prime equal to 31, d is 15. You compute a to the 4th mod 31, not a to the 15th. Here are two C functions, one recursive and the other iterative, which correctly compute: Code: /* Recursive computation of x^m mod n (so n != 0) where m>0. Of course ints involved must be all < MAX_INT and also n^2 < MAX_INT Algorithm works because x^m=(x^(m/2))^2*x^(m%2). At each step the result is reduced mod n. */ int recursivePowmod(int x,int m,int n) { int temp; if (m==1) { return(x%n); } temp=recursivePowmod(x,m/2,n); temp*=temp; if (m&1==1) { temp%=n; temp*=x; } return(temp%n); } /* Computes x^m mod n as in recursivePowmod. Same caveats as there. The validity of this technique can be verified by considering m written in binary. This is more efficient than the above because it takes away the log(m) function calls, but practically there is little difference in efficiency. */ int powmod(int x,int m,int n) { int z=1,y=x; while (m>0) { if (m&1==1) { z=z*y%n; } y=y*y%n; m>>=1; } return(z); } 

Tags 
check, prime, problem 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Please Check my Problem did I do it right! (Must see)  TrimHonduras  Algebra  3  July 21st, 2013 12:27 PM 
Can you check my answer for me on this problem?  shin777  Algebra  1  December 10th, 2011 01:15 AM 
Prime Problem  Mylo  Number Theory  1  April 9th, 2010 09:39 AM 
Prime problem  Crouch  Number Theory  2  January 3rd, 2010 07:42 AM 
Simple word problem check  The_Ys_Guy  Elementary Math  1  December 31st, 1969 04:00 PM 