I was reading Miller-Rabin primality test Wiki and I can't understand something, it says that:
Now, let $n$ be prime with $n > 2$. It follows that $n − 1$ is even and we can write it as $2s \cdot d$, where $s$ and $d$ are positive integers ($d$ is odd). For each $a \in (\Bbb{Z}/n\Bbb{Z})^*$, either
$$a^{d} \equiv 1 \pmod{n}$$
or
$$a^{2^r \cdot d} \equiv -1 \pmod{n}$$
I understand this as, if the result is $1$ or $n – 1$, then it is probably prime.
But in the pseudo code says:
...
if x = 1 then return composite
...
I don't get it.
Also, I get $d$ by doing this:
$$
d = \frac{n-1}{4}
$$
I work in Python, but I'm more of trying to learn all those math symbols such as $(\Bbb{Z}/n\Bbb{Z})^*$
When should I get composite and when probably prime?
Best Answer
First part of answer:
This is correct, because if $x=1$ then all other squaring operations $x := x^2 \pmod{n}$ in the loop leave $x=1$ and therefore $$a^{2^r\cdot d} \not \equiv -1\pmod{n}$$
Second part: You get $s$ and $d$ from $n-1$ with a loop like this (the loop invariant is $n-1= 2^s d)$