# Rabin-Miller Test (Primality)

**URL:** <https://forum.kirupa.com/t/rabin-miller-test-primality/208679>\
**Category:** flash\
**Created:** [December 1, 2006, 4:27am UTC](https://forum.kirupa.com/t/rabin-miller-test-primality/208679 "2006-12-01T04:27:12Z")\
**Posts on this page:** 1\
**Page:** 1

<div class="post-metadata">

**Author:** ![nickcherryjiggz](https://yyz1.discourse-cdn.com/flex011/user_avatar/forum.kirupa.com/nickcherryjiggz/32/2107_2.png) [@nickcherryjiggz](https://forum.kirupa.com/u/nickcherryjiggz)\
**Post date:** [December 1, 2006, 4:27am UTC](https://forum.kirupa.com/t/rabin-miller-test-primality/208679/1 "2006-12-01T04:27:12Z")

</div>

(Note: I’m actually doing this in PHP rather than actionscript, but it seemed to fit here just as well as anywhere else)

I’m making a little 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 actionscript 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.