In my paper I would like to include an example of easy concrete finitary statement which can be easily verified by probabilistic algorithm to any reasonable confidence level, but which looks completely hopeless to prove rigorously.


A candidate example is the statement "$10^{1500} + 2329$ is prime". This can be easily checked with (probabilistic) Miller–Rabin primarity test, while deterministic AKS primality test is too slow to work in this region. However, I am not sure if some other methods (based on elliptic curves, etc.) could be used to rigorously and efficiently prove that this particular number is prime. 


Does there exists $n$ such that Miller–Rabin primarity test works efficiently for numbers of the order $10^n$, but all rigorous methods are expected to work "forever"? 


Alternatively, can you suggest any other concrete statement which works? For example, based on polynomial identity testing? That is, statement "$P=0$" (or "$P \neq 0$") for a concrete polynomial P, simple enough to be included in the paper explicitly.



Example of concrete statement which requires probabilistic algorithm
First of all, there is a conjecture in computer science that BPP = P, i.e., anything that can be done in randomized polynomial time can also be done in deterministic polynomial time. The hope is that you can replace true-random trials with repeated trials with a cryptographically secure pseudo-random number generator. No one can prove that such PRNGs exist, but there are many candidates that are secure as far as anyone knows. A more refined version of the conjecture suggests a quadratic speedup, so that it's still polynomial but not the same degree.


The situation with primality testing is in keeping with this same general picture. The time complexity of Miller-Rabin is $O(d^{2+\epsilon})$, while the time complexity of the rigorous ECPP test is (I am told) $O(d^{4+\epsilon})$. Now ECPP is not Miller-Rabin with repeated trials, but the extended Riemann hypothesis implies that Miller-Rabin with repeated trials would also give you a $O(d^{4+\epsilon})$ time algorithm. My guess is that ECPP is a little slower than ERH-enhanced Miller-Rabin, but it has the advantage that it primality is completely unconditional. In fact, ECPP is also a randomized algorithm, but its answer is always rigorous; the only uncertainty is that it is probably fast. (This is more formally called ZPP and is also called "Las Vegas randomized".)


[This page](http://www.primenumbers.net/prptop/prptop.php) shows current (or current as of a few years ago?) records for finding probable primes using Miller-Rabin. Meanwhile [this page](https://primes.utm.edu/top20/page.php?id=27) shows current records for proving primality using ECPP. A convenient comparison case is given by looking at Wagstaff primes, which are primes of the form $(2^n + 1)/3$. These primes are similar to Mersenne primes in some ways, except that there is no known deterministic primality test like Lucas-Lehmer which is used for the Mersenne case. (In fact Lucas-Lehmer is itself similar to Miller-Rabin and is about as fast; they are both simply refinements of Fermat's Little Theorem.) So, comparing records, $(2^{13,372,531}+1)/3$ was witnessed as probably prime in September 2013, while $(2^{83,339}+1)/3$ was proven to be prime by ECPP one year later, in September 2014. I don't have a specific comparison of computational resources used, but qualitatively it's moot. Taking the $O(d^{4+\epsilon})$ time estimate, it would presumably take about a billion times as much computational power to prove that $(2^{13,372,531}+1)/3$ is prime as to prove that $(2^{83,339}+1)/3$ is prime. In the nearly four years since the smaller number was shown to be prime, the number of digits in ECPP records has grown by a factor of 1.4, which is roughly a factor of 4 in increased computational resources. (Curiously there are 2 or 3 more Wagstaff probable primes in this range, and I'm not sure why they haven't yet been ECPP certified.) I suppose that rigorously proving that $(2^{13,372,531}+1)/3$ is prime is within reach of the US federal budget. But that too is surely moot because a small fraction of that same money could be spent on finding yet bigger probable Wagstaff primes.


