Could G. H. Hardy make a product of two primes so big he couldn't find out which?

Solution 1:

The magic phrase for this problem is 'Zero-Knowledge Proof', and a bit of hunting around suggests that there is in fact a zero-knowledge scheme for the product of two primes - not an exact proof, but a statistical one (so that it can be verified to arbitrarily high probability even with an adversarial prover). From the excerpt for the paper An efficient non-interactive statistical zero-knowledge proof system for quasi-safe prime products by Gennaro, Micciancio and Rabin:

[...] we present the first simple and efficient zero-knowledge proof that an alleged RSA modulus is of the correct form, i.e. the product of two primes.

It looks like the proof goes in stages; first, a zero-knowledge proof that a number $n$ is squarefree by exhibiting the ability to extract $n$th roots of numbers (numbers $n$ that aren't square-free have $\mathrm{GCD}(n,\phi(n))>1$ and thus only a small fraction of numbers will have $n$th roots mod $n$), then a zero-knowledge proof that a number is a product of two prime powers (both of which are inequal to each other and inequal to 1 mod 8), where the verifier supplies a number $x$ and the prover provides a square root for one of $\pm x, \pm 2x$; by quadratic reciprocity, this is always possible for numbers satisfying the condition, whereas products $m$ of three or more prime factors have at most one-eighth of the numbers less than $m$ as quadratic residues, so a randomly-chosen $x$ will fail to have any of $\{\pm x, \pm 2x\}$ be a square at least half the time. Combining the two zero-knowledge proofs gives a zero-knowledge proof for (a subset of) the property 'product of at most two primes', and then combining this with the standard primality tests gives a proof for (a subset of) 'product of exactly two primes'.

Note that this is a statistical proof, though, not an exact one; you can be convinced of the result to an arbitrary degree of certainty but it's not a proof in the classical sense. For more details on zero-knowledge proofs in general, the Wikipedia page is a decent starting point.

Solution 2:

The answer appears to be yes, that we can construct such numbers at present. The techniques that have been used recently have their roots around 1985 when elliptic curves were first applied to cryptography and factorization and when personal computers with RAM by the megabyte became common.

I would like to thank Charles for reminding me that a product of exactly two primes is called a semiprime.

Chris K. Caldwell, a professor at the University of Tennessee at Martin whose current research interest is prime number theory, writes that "small examples of proven, unfactored, semiprimes can be easily constructed." What is easy for him is not so easy for me, but it might not be too hard if I would re-read my copy of Bressoud's Factorization and Primality Testing.

Proven, unfactored semiprimes are called "interesting semiprimes" by Don Reble, a software consultant who took up the problem from (at least his interpretation of) remarks by Ed Pegg, Jr. There are at least two examples online, a 1084-digit interesting semiprime constructed by Don Reble and a 5061-digit interesting semiprime constructed by David Broadhurst, a theoretical high energy physicist.

Reble's interesting semiprime is in a text file that presents some parameters for a proof and the proof itself. It relies on properties of elliptic curves and is therefore currently over my head. Part of Reble's proof is that his semiprime survives a check that it is not a base-two strong probable prime.

Broadhurst's interesting semiprime is in a text file that can be input to Pari. He has written there the relatively elementary conditions and the parameters that he used in order to prove that his number is a semiprime, basing his work on Reble's. He provides the location of a certificate that one of his parameters was proven prime using the free-of-cost, closed-source program Primo by Marcel Martin. Primo is an implementation of elliptic curve primality proving. For suggesting the problem, Broadhurst thanked Reble and Phil Carmody, a Linux kernel developer and researcher in high-performance numerical computing.

Solution 3:

I don't believe this is currently possible. It's easy to test whether a number is prime and much harder to factor, so it's easy to exhibit a number which is a composite but for which no prime factorization is likely to be found. But showing that it is a product of exactly two primes is much harder.

The largest ECM factor found so far is 73 digits. With an extremely large amount of effort one could conceivably show that, with high probability, a given number has no prime factors of 70 or fewer digits.

That means that a number with fewer than 210 digits which is not prime could, in principle, be shown to be semiprime with high probability. But the effort needed to factor the number directly with NFS is smaller than the effort needed to show that it (probably) has no small prime factors.