My Math Forum prime check problem

 Computer Science Computer Science Forum

 June 24th, 2013, 10:28 AM #1 Member   Joined: May 2013 Posts: 34 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 = prime-1 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 == prime-1: return "probably prime",witness else: r = 1 while r < s: v = mod(v*v,prime) if v == prime-1: return "probably prime",witness break else: r += 1 return "composite",witness probprime(213067,17) as far as i can tell, my value for v is correct at every step, yet the prime number above is detected as composite, for almost every witness. 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: 34 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 = prime-1 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 == prime-1: return "probably prime",witness else: r = 1 while r < s: v = mod(v*v,prime) if v == prime-1: return "probably prime",witness break else: r += 1 return "composite",witness probprime(213067,17) apologies, didn't post the whole code.
 June 24th, 2013, 12:37 PM #3 Member   Joined: May 2013 Posts: 34 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: 937 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 Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post TrimHonduras Algebra 3 July 21st, 2013 12:27 PM shin777 Algebra 1 December 10th, 2011 01:15 AM Mylo Number Theory 1 April 9th, 2010 09:39 AM Crouch Number Theory 2 January 3rd, 2010 07:42 AM The_Ys_Guy Elementary Math 1 December 31st, 1969 04:00 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top