Why it is so difficult to perform primality test on huge fermat numbers?

Question

I am not good in computer programming at all, but I know that it will take a lot of times to perform primality test on huge numbers (10 million or billion of digits). But I particularly get interested on fermat numbers,which is numbers of the form $2^{2^{n}}$$+$$1$. And the smallest fermat number with unknown status is F(33),which is over $2.5$ billion digits. I wonder,if I have billion dollars of cash, what can I do,so it would be relatively easy to check the primality of F(33), F(34), or even F(35) with pepin or other tests ?

Answer 1

To make concrete what you have to do to decide whether $F_{33}=2^{2^{33}}+1$ is prime unless someone finds a non-trivial factor :

Pepin's test states that $F_n$ is prime if and only if $3^{(F_n-1)/2} \equiv -1 \ (\ mod\ F_n\ )$

So, you have to square, begining with the number $3$, $2^{33}-1$ times. In each step you can reduce modulo $F_{33}$ , but the magnitude of the numbers , even if reduced to the smallest absolut value (allowing negative residues), will be not much smaller than $F_{33}$.

So you have to do $8,589,934,591$ modulo-multiplications. Nearly all of them involve numbers with magnitude about $F_{33}$ , which has $2,585,827,973$ digits. This is a huge task even with very powerful hardware. The process cannot be parallized (like the factorization of a number) , because you must calculate the squares one by one.

If there is a small factor of $F_{33}$, it will probably be found in near future , but if there is none, it will be very very difficult to check the primilaty of $F_{33}$. Probably, $F_{33}$ is composite.

Look here : http://www.prothsearch.net/fermat.html for more details.