My Math Forum  

Go Back   My Math Forum > Science Forums > Computer Science

Computer Science Computer Science Forum


Reply
 
LinkBack Thread Tools Display Modes
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 = 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.
phillip1882 is offline  
 
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 = 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.
phillip1882 is offline  
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.
phillip1882 is offline  
June 24th, 2013, 12:49 PM   #4
Global Moderator
 
CRGreathouse's Avatar
 
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.
CRGreathouse is offline  
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);
}
johndg is offline  
Reply

  My Math Forum > Science Forums > Computer Science

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





Copyright © 2017 My Math Forum. All rights reserved.