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

This question of course began as a slightly irreverent play on the riddle, "Can God make a stone so big He can't lift it?" Then I wondered about the answer.

Is it possible to exhibit a number that is provably a product of exactly two primes without knowing which primes? More to the point, without having the theoretical and technological means to compute which primes? If so, how is that done, and how old are the results that are needed in order to do it? And if not, does recent theory and technology make it impossible?

• Um, do you mean product of primes or product of two primes? In the first case, just choose any huge number $N$ and with high probability (about $1-1/\ln N$), it will be a product of at least two primes. – Johannes Kloos Mar 30 '12 at 12:57
• Surely, you mean "a product of exactly 2 primes". Otherwise, every even number($\neq2$) is a product of atleast two primes, so tell me how large a prime you want. – Ravi Mar 30 '12 at 12:57
• What do you mean by "is provably a product of primes"? Surely $2^N + 1$ is a product of some primes, but for large $N$ finding those primes is hard. – TMM Mar 30 '12 at 12:58
• The fundamental theorem of arithmetic says that every number is a product of primes. So just pick your favourite way of describing huge numbers… – Seamus Mar 30 '12 at 13:02
• Tell me more of this "Fundamental Theorem" of which you speak. Just kidding, yes of course I meant exactly two primes. Thanks. – minopret Mar 30 '12 at 13:07

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.

• I think the question requires a constructive proof - yours seems to need you to have the number to be tested already in hand. – Random832 Mar 30 '12 at 17:09
• "a bit of hunting around suggests that there is in fact a zero-knowledge scheme for the product of two primes" - There is a theorem in cryptography that states that every statement regarding hidden knowledge has a zero-knowledge proof. So yes, a zero-knowledge proof definitely exists. – BlueRaja - Danny Pflughoeft Mar 30 '12 at 17:12
• However, I'm not sure this meets OP's requirements - Zero Knowledge proofs require the proving-party to already have the knowledge. Thus, if I have a product of two large primes (semiprime) and I know both primes, I can prove to you that the number is semiprime, and further that I know the prime-factors, without giving you any information about what those factors are. However, if neither of us knows the factors, then a zero-knowledge proof won't help us determine whether the number is the semiprime. – BlueRaja - Danny Pflughoeft Mar 30 '12 at 17:16
• @BlueRaja-DannyPflughoeft Agreed - I was taking 'exhibit' in the sensze of 'exhibit to a random person on the street'; that is 'I tell you this number is a semiprime and I will prove beyond a reasonable doubt that it is a semiprime, but you won't have the means to determine its factors'. The question of 'are there numbers that we can know to be semiprime without knowing their factors' is certainly a more difficult one, but I wanted to provide a positive answer for at least one version of OP's statement. – Steven Stadnicki Mar 30 '12 at 17:41
• Right, I was looking for a product of exactly two primes for which we may presume that no one knows the factors. This answer addresses an interesting but separate question. Considering the number of votes this answer has received, this other question would be a valuable addition to math.stackexchange.com. – minopret Apr 1 '12 at 19:13

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.

• I'm not sure if this meets the criteria of the question: don't you need to know the factorization of N to construct the number? Still, it's interesting regardless. – Charles Apr 4 '12 at 1:10
• It's claimed you needn't have the factorization (although Broadhurst does) but as I admitted, I wouldn't actually know. I'm certainly willing to remove the "accepted" status from my answer if we become aware of a flaw, or simply better information. – minopret Apr 4 '12 at 11:37
• @minopret: I'm fine with you getting the check, I just wanted to point out that there are different interpretations of the question and thus our seemingly contradictory answers are, in fact, both valid (just addressing different things). – Charles Apr 4 '12 at 14:04

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.

• "Semiprime." Aha, "interesting semiprimes". – minopret Mar 30 '12 at 16:36
• Anyhow, it is worth mentioning that this approach makes the problem easier than the prime factorization of an integer... One could also calculate $10^{70} \mod n$, then this is an unit if and only if $n$ has at most two prime factors... – N. S. Apr 1 '12 at 19:13
• What is NFS?... – leo Apr 1 '12 at 19:24
• @leo: The Number Field Sieve, the asymptotically-fastest known method for factoring large numbers. – Charles Apr 1 '12 at 21:06
• @Charles, thanks for the clarification – leo Apr 2 '12 at 18:16

Depends on what you mean by 'exhibit a number'. How about $14$ iff for all $N<{10^{10^{99999}}}$, $2N$ is a sum of two primes, else $15$?

This is a well-defined, computable and unique number.

In what sense is the string $56566633746456456$ a better representation of a number then "$x=14$ iff Goldbach is true for all $N<{10^{10^{99999}}}$, else $x=15$", other then the artificial human base-10 convention ?

• As someone had pointed out before this answer was deleted earlier, this does not exhibit a number, it exhibits a function. – Graphth Mar 30 '12 at 17:02
• This is not exhibiting a number. This is exhibiting a function whose value you cannot compute with current means of mathematics. – Asaf Karagila Mar 30 '12 at 18:49
• This is a well-defined number. It is either 14 or 15; we don't know which. Please will those who are seeing a function specify the domain $X$, the codomain $Y$, and the subset of $X\times Y$ that is the function. – John Bentin Mar 30 '12 at 21:24
• How does this nonsense answer have anything to do with the OP? – user641 Mar 31 '12 at 18:19
• It looks more like a well-defined number if you write it as $14 + \bigvee_{n = 1} ^ {10^{10^{9999}}} f(n)$ where $f(n) = 1$ if $2n$ cannot be written as a sum of two primes and $f(n) = 0$ otherwise. – guy Apr 1 '12 at 20:18