Is it practical to find actual very large prime numbers (such as those up to 100 digits)?

Question

I just asked How to find extremely large BigInt prime numbers exactly in JavaScript? and was explained that all I ever can hope for is a "probable" prime, not an exact/actual prime if they are that large (up to 100 digits). To me, the reason for that would be because it takes too long to compute the possible factors of the potential prime (which is what my JS code was saying to me). Is this true? Is there no way to find an exact/actual (i.e. non- "probable") prime number that is 70 to 100 digits long? If it is possible, how is it done (at least at a high, non-software/non-code level)? If it is possible, can we go to larger integers like up to 65536 digits? If not, why can't it be done/calculated with certainty, is there no possible way?

Answer 1

It is absolutely practical and can be done deterministically. The AKS (Agarwal Kayal Saxena) primality test is a deterministic test which proves primality. It is also unconditional (does not depend on any unproved but widely believed hypothesis). The AKS test's complexity has been improved over time and is by now of order $O(t^6)$ where $t$ is the bitsize of the prime candidate you are testing (so $t=100/\ln 2$ for your 100 digit number).

So, you can randomly choose an odd integer of 100 digits and run AKS on it. After repeating this roughly $\ln 100$ times (density of primes of that size by the Prime Number Theorem) you are likely to discover a provable prime of the form you like.

AKS Paper from the Annals of Mathematics is available here. Use google for much more information on AKS.

Answer 2

Not quite $70$ digits ("only" $61$) but the integer $$p=2~000~000~000~000~000~000~030~000~000~000~000~000~000~500~000~000~000~000~000~007$$ Is prime. And, as per the request in your other question, it is also very clear that $$\operatorname{mod}(p,4)=3$$

Answer 3

There are numbers that have properties that make them interesting for the search of large primes. They provide quickly large numbers and we can apply efficient primality tests. For example Mersenne numbers of the form $2^n-1$ can only be prime if n is prime (a necessary condition) and we can use the Lucas-Lehmer primality test on them.

So 521 is prime and $2^{521}-1$ is also prime, it is a 157 digit prime. But we can fine huge prime like $2^{82 589 933}-1$ which has 24 862 048 digits (base 10).