# Rabin-Miller compositeness

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

• 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? – hardmath Jul 22 '15 at 11:26
• $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 – 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!)