Miller test for longints

As we know Zp, which is a set of numbers {1,2,...,p-1} with multiplication modulo p, where p is odd prime, is a field. Because of this, we can easily prove that there exist only two numbers t, such that t^2=1 (counting in Zp). We do it by assuming that in set {1,2,...,(p-1)/2} there exist two t's with property above and then we can see contradiction. We can easily name those t's: it's 1 and p-1. Miller test is based on this notice and on Fermat's Theorem. In this test we firstly choose a random number a from {1,2,...,p-1}. Then we compute a^(p-1). As Fermat's Theorem says, it should be 1. Unfortunately, there are some numbers, called Carmichael ones, that pass this test every time in spite of the fact, that they are composite. Fortunately, it is proved that if a number is Carmichael's one, it has many such t's as explained above. So simply when computing a^(p-1) in each step we also check if we've not found any not trival t, which in a square gives 1.

Because of problems with range due to using longints, this test, as implementated below can't be used for numbers bigger than range of integer. To make this test really useful, we must compute operations on big numbers, which is the next problem.

To see source code click here.

To see that it really works, use below: