I'm making a little php encryption page, and am stuck on the isPrime function. I'm vaguely aware of how the Rabin-Miller test works, and I've read several algorithms (in words) for it. Having never been taught the material, though, I'm confused by some of the notation (=, 1 (mod n)) and I can't figure out exactly what I need to do. I think that the coding of such a prime test would be short and simple (possibly less than 20 lines), but I'm just not exactly sure what needs to be done. Here is one description of the algorithm... ************ Given (b,n) where n is the number to test for primality, and b is randomly chosen in [1, n -1]. Let n - 1 = (2^q) * m, where m is an odd integer. If either (a) b^m = 1 (mod n) or (b) there is an integer i in [0, q -1] such that b^(m*2^i) = -1 (mod n) then return "inconclusive" else return "n is composite" ************ Ok, so n is obvious...the number I want to test. b is easy as well...a random number within the range 1 through n-1 let n - 1 = ...ok, good up until here (2 ^ q) * m now, this is where I get confused...am I to arbitrarily pick an odd integer m and solve for q? then comes this line... b^m = 1 (mod n) I think the = means is congruent to...but it seems like it is practically an equal sign...just one that has several possible answers (4 % 3 = 1, 7 % 3 = 1, etc.) anyway...then comes 1 (mod n)...does this mean 1 % n ? if so, wouldn't any value of n other than 1 return 1? 1 % 5 = 1, 1 % 1521 = 1, 1 % 352023059 = 1? If anyone could clear some of this up, I'd be greatly appreciative. If I could see some PHP code of the for loop for this operation, I think that would clear things up much better. In all the forms I've seen it this far, it's just not clicking with me.
There is a prime number generator in PHP at http://www.phpfreaks.com/quickcode/Prime-number-generator/547.php and here http://www.fedtrek.com/Prime_Numbers-view_source-yes.html
Thank you for the reply. Unfortunately, I cannot use this method of checking for primes. The numbers I'll be dealing with are 300+ digits long and checking for every multiply just won't work in this situation. It must be (to my knowledge) the Rabin-Miller test, or something similar.
I have been doing some poking around on this topic and I have found that the Rabin-Miller test correctly predicts that prime numbers are prime numbers; but that it also mistakently predicts that some very large non-prime numbers are prime numbers. Candidate numbers then need to be run through a second test to know for sure if it they are primes. A PHP imple,entation can be found here: http://www.phpbuilder.com/snippet/detail.php?type=snippet&id=745