Finding the smallest prime that is larger than $10^{100}$ or $10^{10^{10}}$

Question

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

Answer 1

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

Answer 2

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.

Answer 3

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.