Find a witness Rabin-Miller of compositeness of $n=25$

Can anyone explain and show me a way on how to solve this question?and generally how to find witness Rabin-Miller

  • $\begingroup$ You don't seem to have looked into what the word "witness" means in the context of the Rabin-Miller primality test, so it's hard to guess what help you actually need. Is the phrase "strong pseudo-prime" something you know how to define? $\endgroup$ – hardmath Jul 22 '15 at 11:26
  • 1
    $\begingroup$ $25-1=24=8*3$ look for some $a<25$ such that $a^{3}\equiv 1 \mod 25$ or one of the numbers $a^{3},a^{3.2},a^{3.4}$ is $\equiv -1\mod 3$ , you can try them one by one (or at random), we know that approximately $75%$ of the numbers will work $\endgroup$ – Elaqqad Jul 22 '15 at 11:28

This is a somewhat stupid case for Miller-Rabin because you should assume that n is not a square. Anyway. Let $n=25$ and $a=2$ the smallest possible candidate, then $n-1=d\times 2^s = 3\times 2^3.$ Now compute $$x_0 \equiv a^d \equiv 2^3 \equiv 8 \pmod{25}$$ $$x_1 \equiv x_0^2 \equiv 14 \pmod{25}$$ $$x_2 \equiv x_1^2 \equiv 21\pmod{25}$$ Thus $a^d\not \equiv 1 \pmod {25}$ and $x_r \equiv a^{2^r d}\not \equiv -1 \pmod {25}$ for $0\le r \le s-1.\,$ Therefore $a=2$ is a witness for the compositeness of $25$.

Regarding the second part: Obviously, for general $n\,$ you cannot always find a Miller-Rabin witness for the compositeness of n! (otherwise there would be no primes!)


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.