2

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 ?

Bulldogisthebestdog
  • 21
  • Pepin's test is fast but still you have to mange many modulo multiplications of very large numbers. Much money would give you access to faster programs perhaps, but you still would take quite a long time to finish the test. Curious fact : Fermat conjectured that all Fermat numbers are prime, now some mathematicians conjecture that there are no Fermat primes for $n>4$. – Peter Jan 13 '16 at 17:58
  • If I remember right, a super-computer ran about ten days to prove a Fermat number (I do not know which) to be composite. This was at a time where computers were magnitudes slower than today. It is debateable, whether such calculations have reasonable merit. – Peter Jan 13 '16 at 18:55
  • Miller-rabin python implementation never gets out of pow(a,d,n) imagine an int with 100,000 digits, a is. random that can be close to that int, d too, n too. pow will create an in with $100,000^2$ digits. We need primality tests that do not use pow (or makes it efficient) Fermat's idea is great but not realistic for our computing power. – juanmf Jun 17 '22 at 18:58

1 Answers1

3

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.

Peter
  • 84,454
  • Can the squaring itself be parallelized, so that OP could spend his billion dollars on thousands computers and get it done faster? I'm thinking of the Schönhage–Strassen algorithm, in which case it seems to be the same as parallelizing a DFT, and I'm not sure about that either. – Dan Brumleve Jan 13 '16 at 18:32
  • Maybe I missed something, but I do not have an idea how the fast-fourier-transformation (the fastest algorithm for such huge numbers) could be parallized. Probably the algorithm would be faster on a single machine than a parallized algorithm using the naive multiplication method. But as I said, I might underestimate todays possibilities. – Peter Jan 13 '16 at 18:48