# Miller-Rabin primality test, begginer reading pseudo code

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?

• I dont want to read other code, becouse I'm doing project Euler, which will totally spoil it if i read any code at all. I'm willing to understand why it says $a^{d} \equiv 1\pmod{n}$ and in the pseudocode says if x = 1 then return composite Sep 20 '13 at 0:55
• Well, have you read any other sources on the algorithm including the paper? Sep 20 '13 at 0:56

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;

• Can't i write d like this: d := (n-1) / 4 And s will always be 2, so 2^2 * d I will still produce a number n-1, is this reasonable? Sep 20 '13 at 14:06
• No is is wrong, take e.g. $n=7$ where $n-1=6$ is not a multiple of 4! Sep 27 '13 at 11:07