I'm having problems with an algorithm and I was hoping you could help me.
If you've been asking why I didn't post on a programming forum, the answer is "I did", but they sent me to a math board, so here I am...
The algorithm I'm having trouble with is Miller-Rabin primality test .
What I understand is that for the equation a^d = 1(mod n) we get two solutions: 1 and -1. That means that (a^d)/n is either 1 or -1.
But the equation a^(2^r*d) = -1(mod n) has only one solution: -1.
Tell me if I'm wrong.
What I don't understand is why a^d = 1(mod n), why not a^d = -1(mod n)?
Where did they get these equations from?
Thank you very much for your time.