As an exercise for myself, I'm implementing the Miller-Rabin test. (Working through SICP). I understand Fermat's little theorem and was able to successfully implement that. The part that I'm getting tripped up on in the Miller-Rabin test is this "1 mod n" business. Isn't 1 mod n (n being some random integer) always 1? So I'm confused at what a "nontrivial square root of 1 modulo n" could be since in my mind "1 mod n" is always 1 when dealing with integer values. What am I missing?
3 Answers
Related