Given num > 3
, you want: d, r s.t. pow(2,r) * d = num - 1, where d is odd
.
You are effectively counting trailing zeroes from num - 1
, to remove factors of 2
. However, after that loop, you know pow(2,r)
is a factor of num - 1
. Hence:
d = (num-1) % Math.pow(2,r);
will always yield: d = 0
. I suspect you meant to replace %
(mod) with /
(div) here; otherwise, Math.pow(a[k],d)-1
will always yield (0)
, and the inner loop will never be executed.
As others pointed out, some simple trace statements or assertions would have found these errors. I think you have other issues, such as integer overflow. The loop for testing against the a[]
candidates (the a-SPRP test) looks completely wrong to me.
Perhaps you've got the algorithm from Wikipedia, I prefer the more detailed reference in The Handbook of Applied Cryptography: 4.2.3: Miller-Rabin test, Algorithm: 4.24.