# Rabin-Miller Test (Primality)



## nickcherryjiggz (Nov 21, 2006)

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 (or C++) 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.


----------



## drgoodtrips (Nov 11, 2006)

First off, the three bar sign does, in fact, mean congruent, and is often used by convention when discussing modulus operations (since equality isn't strictly appropriate in such a process).

Secondly, you don't arbitrarily pick m and q. Let's say that I give you the odd number 101 as input n. So, n-1 is 100. You would then go through and divide by 2 until you couldn't anymore. That is...

100 = ...
50 * 2 = ...
25 * 2^2 ...

and we're done. q is 2 and m is 25. To extrapolate this, for your odd number n, here is some pseudo-code:


```
int temp = n - 1
int q = 0;
do while temp % 2 = 0
  temp /= 2
  q++
loop
```
At the end of this, "temp" will be your m value and q, obviously, will be q.

Finally, b^m (congruent) 1 mod n is simply saying that b^m % n is always 1. Or, if you raise b to the m power and divide by n, there will always be a remainder of 1.

Hope that helps


----------

