(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.