Hi,

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.

Carmen