Miller-Rabin primality test, begginer reading pseudo code

Question

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?

Answer 1

First part of answer:

...
if x = 1 then return composite
...

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)$

d := n-1;   
s := 0;   
while even(d) do begin
  d := d/2;
  s := s+1;   
end;