6
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ 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 $\endgroup$
    – dragons
    Sep 20 '13 at 0:55
  • 1
    $\begingroup$ Well, have you read any other sources on the algorithm including the paper? $\endgroup$
    – Amzoti
    Sep 20 '13 at 0:56
1
$\begingroup$

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;
$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – dragons
    Sep 20 '13 at 14:06
  • $\begingroup$ No is is wrong, take e.g. $n=7$ where $n-1=6$ is not a multiple of 4! $\endgroup$ Sep 27 '13 at 11:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.