33
$\begingroup$

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?

  • 0
    Not G.H. Hardy, but "Gauss can factor a two million digit semiprime in his head!" http://www.gaussfacts.com/view/Mathematics/8252013-04-25

4 Answers 4

0

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 ?

  • 3
    @Graphth Who are you trying to convince? I know what I typed, because I had the answer in my clipboard and copied it exactly over. I understand its hard on your tiny minds to witness the genius of my answer.2012-04-15
17

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.

  • 2
    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.2012-04-01
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.

  • 0
    @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).2012-04-04
6

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.

  • 0
    @Charles, thanks for the clarification2012-04-02