Curious about methods for finding Goldbach pairs for large even numbers

Question

I am exploring the question of efficiently identifying two prime numbers that sum to a given large even number, particularly for even numbers exceeding 100 digits. While brute force and precomputed prime tables are common approaches, I am curious whether there exists a deterministic algorithm capable of solving this problem, given sufficient computational resources.

Specifically, I am interested in methods that:

Avoid reliance on probabilistic techniques (e.g., random sampling of primes).
Operate deterministically to find a valid prime pair for any even number within the given constraints.
Scale efficiently as the size of the even number increases.

Are there any existing algorithms or advancements in this area that can achieve this deterministically? Alternatively, is there ongoing research into related methods for efficiently handling this problem?

I would appreciate any insights or pointers to theoretical or computational techniques that address this challenge. Thank you for your time and expertise.

Answer 1

Cramer's random model suggests that the probability that $a, n-a$ are both primes is $\frac{1}{\log(a)\log(n-a)}$. For fixed $n$, this is is maximized for $a$ small (or $n-a$ small) suggesting that the most efficient method would be to first check if $n-3$ is prime, then $n-5$, then $n-7$, and so on.

For $n$ enormous and $a$ small, the natural approach would be to use a precomputed table for small primes $a$ and a primality test for large primes $n-a$. You want to use deterministic approaches, but thankfully there is the AKS deterministic primality test.

Following Jakob Streipel's suggestion, I observe that at least one Goldbach verification, the one by Tomás Oliveira e Silva, and probably most/all of them focus on finding the least $a$ such that $a$ and $n-a$ are both primes, and therefore use a similar overallstrategy.

The heuristic suggests that almost all numbers $n$ should have a prime solution $a$ less than about $\log n \log \log n$. For $n< 4 \cdot 10^{18}$, the worst case has $a < 10^4$. I therefore suspect that for $n$ of $100$ digits one should still only need to take $a<10^5$ or so, so one should need to use only a tiny precomputed table and run the primality test at most 9592 times, which seems fine.

I'm not sure what you mean by "a deterministic algorithm capable of solving this problem, given sufficient computational resources". If you want an algorithm that is guaranteed to solve the problem, assuming a prime pair exists, then you may need to provide sufficient computational resources to search every prime up to $n/2$.