How to compute really large primes which are specified as expressions?

Question

I found a list of the 5000 largest primes, but unfortunately I don't see the prime, just an expression for most of them:

1716  704*249^354745+1                  850043 L5410 2019 
1717  1001*2^2822037+1                  849521 L1209 2019 
1718  84466*5^1215373-1                 849515 L3562 2013 
1719  97*2^2820650+1                    849103 L2163 2013 
1720  107*2^2819922-1                   848884 L2484 2013 
1721  84256*3^1778899+1                 848756 L4789 2018 
1722  45472*3^1778899-1                 848756 L4789 2018 
1723  14804*3^1778530+1                 848579 L4064 2021 
1724  497*2^2818787+1                   848543 L4842 2019 
1725  97*2^2818306+1                    848397 L3262 2013 
1726b 313*2^2817751-1                   848231 L802  2021 
1727  177*2^2816050+1                   847718 L129  2012 

How can you compute the actual BigInt? Is it not possible, are they too large?

Darn :)

Is there an algorithm that could accomplish it? If not for these, then for other very large primes?

Answer 1

You have to cast the ingredient numbers to BigInts before you try to compute the expression. In the expression you wrote, the computer is attempting to compute the huge prime and then cast the result to a BigInt, which is why it overflows (as the input is an int, rather than a BigInt).

It should read something like this:

BigExp(BigInt(30059800), 131072).addOne()

---

However, most of the largest known primes have many millions of digits, so even computing the result this way may be intractable. You can compute the lowest order digits using modular arithmetic; For example, the largest known prime ends with

$$\ldots4037951210325217902591.$$

and this was computed by computing powers of $2$, reducing the result $\bmod 10^N$ for a large pre-selected $N$. As for computing the leading digits, it may be intractable.