Miller-Rabin primality test for $2^{32}+1$

Question

How can I prove that $2^{32}+1$ is composite number using Miller-Rabin primality test?

I can't find a solution which verify the hypothesis of theorem.

Answer 1

Let $n=2^{32}+1,\, a=3$. You can show that $a=3$ is a witness for compositeness of $n$, i.e. $n$ is not a strong pseudo prime to base 3.

Here is the calculation: Decompose $n-1$ as $n-1=d\times 2^s = 1\times 2^{32}$, i.e. $d=1,\,s=32$. Then you have $a^d\not \equiv 1 \pmod {n}$, now verify that $x_r \equiv a^{2^r d}\not \equiv -1 \pmod {n}$ for $0\le r \le s-1.$ Note that $x_{r+1}\equiv x_r^2 \pmod {n}$.

In the table I have listed $r$ and $x_r \pmod {n}$

   r  x_r mod n
   1  9
   2  81
   3  6561
   4  43046721
   5  3793201458
   6  1461798105
   7  852385491
   8  547249794
   9  1194573931
  10  2171923848
  11  3995994998
  12  2840704206
  13  1980848889
  14  2331116839
  15  2121054614
  16  2259349256
  17  1861782498
  18  1513400831
  19  2897320357
  20  367100590
  21  2192730157
  22  2050943431
  23  2206192234
  24  2861695674
  25  2995335231
  26  3422723814
  27  3416557920
  28  3938027619
  29  2357699199
  30  1676826986
  31  10324303

Answer 2

As your example has already been solved therefore, I am gonna explain the idea behind Miller-Rabin primality test.

The test is based on Fermat's little theorem i.e. a large positive odd integer n is pseudoprime to the base b if $b^{n-1} \equiv 1 \pmod{n}$ where gcd$(n,b)=1$ or simply $b\in(\mathbb{Z}/\mathbb{nZ})^*$. Which implies that $$b^{(n-1)/2} \equiv \pm1 \pmod{n} \\ b^{(n-1)/4} \equiv \pm1 \pmod{n} \\ \vdots \qquad \qquad \vdots \qquad \qquad \vdots \\ b^{(n-1)/2^{s}} \equiv -1 \pmod{n}$$ Where $((n-1)/2^{s})^{th}$ power is odd.

In practice we take $n-1=2^st$ where $t$ is odd integer. Then for any integer b, $0<b<n$, we check the existence of any of the following two conditions

1) $b^t \equiv 1 \pmod{n}$ or

2) $b^{2^r}t \equiv -1 \pmod{n}$ where $0\leq r < s$

Then $n$ is called a strong pseudoprime to the base b.

The probability of $n$ to be prime gets higher and higher as more and more random $b$s satisfy any of the above condition.