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

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.

## 2 Answers

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

• Where do you made all the modular calculus?Online?Thank you! – alexb Dec 7 '15 at 15:15
• No, I simply put a writeln statement in my SPSP routine. But you can do it easily with a scripting language / interpreter, e.g. with Pari/GP n=2^32+1, y=Mod(3,n), y=y^2, y=y^2 etc – gammatester Dec 7 '15 at 15:38

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.