4

Is there a known tractable way to find the smallest prime number that is larger than $10^{100}$?

I'm asking because I want to use this as an example for a task that requires an incredible amount of computation power, and I don't want to embarrass myself :)

Dietrich Burde
  • 130,978
Ofer
  • 63
  • Other than trial and error, not really. – Arthur Mar 05 '18 at 20:44
  • Let me point out a potential risk in this example: There are choices for large $a$ such that the question 'Is there a known tractable way to find the smallest prime number that is larger than $a$' has a positive answer. E.g. if $a+1$ happens to be a Mersenne prime in the region of hundreds of digits. Hence I'd suggest asking the question 'What is the list of primes $\le a$?' instead. The advantage of the latter question is that you can't have freak positive answers if you happen to choose $a$ in an unfortunate manner. – Stefan Mesken Mar 05 '18 at 20:54
  • There is a program called Primo that proves primality and can, I think, be downloaded on to a home machine. Once you have a few candidates, it should not take the program very long to decide each; i understand it can do up to $10^{5000}$ ... http://www.ellipsa.eu/public/primo/primo.html – Will Jagy Mar 05 '18 at 20:56
  • With Pari/gp including a primality proof: v=nextprime(10^100); if(isprime(v),print(v),print("BPSW counterexample found!")) taking less than 100 milliseconds. Once over 1000 or so digits, Primo is the better answer for the proof portion. Primo works past 30k digits, though anything over 20k is going to be a long slog. – DanaJ Mar 05 '18 at 20:59
  • 1
    Or Wolfram Alpha, which gives you the answer in about as long as it takes to connect to the server and back: $10^{100} + 267$. – The Short One Mar 05 '18 at 21:54
  • @DanaJ I think to prove the primilaty, the command isprime(v,2) is necessary, but the slowdown is minimal for 100-digit-numbers. – Peter Mar 06 '18 at 10:18
  • @Peter, the flag is just forcing a particular algorithm. It proves primality in either case, just possibly with a different algorithm based on the input. – DanaJ Mar 09 '18 at 06:36

3 Answers3

5

This requires very little computational power -- it takes less than a millisecond on my Macbook. If you insist on a proof, that takes adds 50-100 millseconds.

Now $10^{10000}$ is more interesting. Still quite fast for find the next probable prime, but a proof is going to take a non-trivial amount of time (maybe a couple hours). Another factor of 10 and the nextprime is not too hard, but the proof is not computationally feasible (with current methods and resources).

vadim123's answer points out the easy fix of $10^{10^{10}}$. That's going to make even the nextprime operation computationally extraordinarily difficult with today's methods/resources.

DanaJ
  • 2,999
  • are you talking about $10^{100} + 267 ; ?$ The other answer seems to be saying it worked, with proof. I don't see an immediate way to put primo on my home machine, it is ubuntu 16.04 but is 32 bit. – Will Jagy Mar 05 '18 at 21:04
  • Yes, nextprime(10^100) = 10^100+267 can be found very quickly (there are separate questions about how to best do it), using a good probable prime test like BPSW. That's what nextprime in Pari/GP and Perl/ntheory uses. For the proof we could use Pari/GP (APR-CL, and ECPP in dev), or Perl/ntheory (ECPP), or Primo (ECPP). Primo adds the whole user interface overhead and is slower at this tiny size, but has a better growth rate so faster at ~500-1000 digits and beyond. I run Primo on my Fedora machines but they're all 64-bit. – DanaJ Mar 05 '18 at 21:09
  • Thanks. I do have a version og Pari/gp, I should see what I already have in the way of proving primes. I did answer a question, maybe a month ago, where it would have been nice to confirm some probable primes from, I guess, $10^{20}$ up to about $10^{45}$ Found it https://math.stackexchange.com/questions/2660814/find-p-q-prime-numbers-s-t-pp2-p10-q-2017/2661097#2661097 – Will Jagy Mar 05 '18 at 21:17
  • 1
    For numbers that size, Pari/GP works well, or if you want to plug into a GMP program I'd recommend mpz_aprcl which includes a decent BPSW plus APRCL proof code. It's super convenient. My ECPP is possible to plug in but isn't very convenient right now. It does create a standalone executable that does proofs (and mpz_aprcl can be plugged in if you want that available). – DanaJ Mar 05 '18 at 21:22
3

Finding the prime is easy with pseudo-prime tests, the result is $10^{100}+267$. The greater task is to prove this prime with a real prime test.

But even with an old Windows version of Primo this is done in milliseconds.

gammatester
  • 18,827
3

Here's an easy fix to the OP's problem: instead of $10^{100}$, use $10^{10^{10}}$. It's only slightly longer to write, but much, much larger as a number (and the prime question extremely hard to answer).

vadim123
  • 82,796