1
$\begingroup$

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?

$\endgroup$
1
  • 1
    $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$
    – Xander Henderson
    Jan 12 at 16:36

3 Answers 3

3
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ I tried doing what I think is something similar to what you are suggesting here (Miller test to filter out candidates, and then AKS test using the I guess broken code? I updated that AKS code to work with BigInts, so maybe that helps, not sure). I ran it for 3 minutes but found no primes. I will check out some more AKS resources and your link. Thanks! FWIW the miller test is fast (thousands of candidates a second). $\endgroup$
    – Lance
    Jan 12 at 15:37
  • $\begingroup$ of course miller is much faster but it is randomized--you may be happy to live with a small probability that what you find is not a prime $\endgroup$
    – kodlu
    Jan 12 at 16:42
  • $\begingroup$ I am not happy with "probable" primes haha, I want actual primes guaranteed. $\endgroup$
    – Lance
    Jan 12 at 19:55
3
$\begingroup$

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).

$\endgroup$
1
  • $\begingroup$ Interesting, thanks for pointing out I never thought of that. $\endgroup$
    – Lance
    Jan 12 at 15:27
0
$\begingroup$

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$$

$\endgroup$
1

Not the answer you're looking for? Browse other questions tagged or ask your own question.