Proof the following statement or give a counterexample:

Let $n$ be a natural number.

If $n \equiv 1 \mod 4$ and $4^\frac{n-1}{4} \equiv -1 \mod n$, then $n$ passes the Miller-Rabin test to the basis 2

I strongly believe that the statement is true but could not find a proof for it.

The Miller-Rabin test works as follows:

Let $n$ be an odd number (true in our case) and $a$ the basis ($2$ in this question). Calculate $d$ (odd) and $j$ such that

$$n-1=d \cdot 2^j$$.

We then check if either

$$a^d \equiv 1 \pmod n$$

or (for some $r$ with $0 \leq r \leq j$)

$$a^{d \cdot 2^r} \equiv -1 \pmod n.$$

which must always be the case if $n$ is prime.

  • $\begingroup$ For casual readers: The Miller-Rabin test is a primaility test explained here: en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test $\endgroup$ – Mark Fischler Aug 27 '16 at 13:22
  • $\begingroup$ WHy the downvote? I upvoted to compensate. $\endgroup$ – Mark Fischler Aug 27 '16 at 13:29
  • $\begingroup$ You give a parenthetical remark that the base is "2 in this question". Is that the assumption? If so, it belongs more explicitly in the statement of the question itself. Are you trying to prove that any $n$ which satisfies the conditions is a base-2 strong pseudoprime? $\endgroup$ – John Coleman Aug 27 '16 at 13:46
  • $\begingroup$ @John Coleman. Yes that is the assumption. Sorry, I accidentally deleted this part when editing the question. My bad. $\endgroup$ – sigfood Aug 27 '16 at 13:50

Since $4^\frac{n-1}{4} = 2^\frac{n-1}{2}$, and $\frac{n-1}{2} = d*2^{j-1}$, Miller-Rabin is passed with $r = j-1$.


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.