34
$\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?

$\endgroup$
9
  • $\begingroup$ 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. $\endgroup$
    – Johannes Kloos
    Commented Mar 30, 2012 at 12:57
  • $\begingroup$ 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. $\endgroup$
    – Arkady
    Commented Mar 30, 2012 at 12:57
  • 1
    $\begingroup$ 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. $\endgroup$
    – TMM
    Commented Mar 30, 2012 at 12:58
  • $\begingroup$ The fundamental theorem of arithmetic says that every number is a product of primes. So just pick your favourite way of describing huge numbers… $\endgroup$
    – Seamus
    Commented Mar 30, 2012 at 13:02
  • 10
    $\begingroup$ Tell me more of this "Fundamental Theorem" of which you speak. Just kidding, yes of course I meant exactly two primes. Thanks. $\endgroup$
    – minopret
    Commented Mar 30, 2012 at 13:07

4 Answers 4

Reset to default
18
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ I think the question requires a constructive proof - yours seems to need you to have the number to be tested already in hand. $\endgroup$
    – Random832
    Commented Mar 30, 2012 at 17:09
  • $\begingroup$ "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. $\endgroup$
    – BlueRaja - Danny Pflughoeft
    Commented Mar 30, 2012 at 17:12
  • $\begingroup$ 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. $\endgroup$
    – BlueRaja - Danny Pflughoeft
    Commented Mar 30, 2012 at 17:16
  • 6
    $\begingroup$ @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. $\endgroup$
    – Steven Stadnicki
    Commented Mar 30, 2012 at 17:41
  • 2
    $\begingroup$ 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. $\endgroup$
    – minopret
    Commented Apr 1, 2012 at 19:13
15
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ 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. $\endgroup$
    – Charles
    Commented Apr 4, 2012 at 1:10
  • $\begingroup$ 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. $\endgroup$
    – minopret
    Commented Apr 4, 2012 at 11:37
  • $\begingroup$ @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). $\endgroup$
    – Charles
    Commented Apr 4, 2012 at 14:04
  • $\begingroup$ I think Reble must have also known the factorization of his semi-prime number. Generating a elliptic curve primality test certificate that isn't as strong as usual, so it only guarantees that there are at most two factors instead of one, is a neat idea. But AFAIK finding a certificate requires finding the number of points on a given elliptic curve modulo $N$, which cannot be done without factoring $N$ link.springer.com/content/pdf/10.1007%2FBFb0054116.pdf. $\endgroup$
    – qbt937
    Commented Sep 20, 2020 at 3:35
6
$\begingroup$

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.

$\endgroup$
5
  • 2
    $\begingroup$ "Semiprime." Aha, "interesting semiprimes". $\endgroup$
    – minopret
    Commented Mar 30, 2012 at 16:36
  • $\begingroup$ 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... $\endgroup$
    – N. S.
    Commented Apr 1, 2012 at 19:13
  • $\begingroup$ What is NFS?... $\endgroup$
    – leo
    Commented Apr 1, 2012 at 19:24
  • $\begingroup$ @leo: The Number Field Sieve, the asymptotically-fastest known method for factoring large numbers. $\endgroup$
    – Charles
    Commented Apr 1, 2012 at 21:06
  • $\begingroup$ @Charles, thanks for the clarification $\endgroup$
    – leo
    Commented Apr 2, 2012 at 18:16
-1
$\begingroup$

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 ?

$\endgroup$
20
  • 5
    $\begingroup$ As someone had pointed out before this answer was deleted earlier, this does not exhibit a number, it exhibits a function. $\endgroup$
    – GeoffDS
    Commented Mar 30, 2012 at 17:02
  • 5
    $\begingroup$ This is not exhibiting a number. This is exhibiting a function whose value you cannot compute with current means of mathematics. $\endgroup$
    – Asaf Karagila ♦
    Commented Mar 30, 2012 at 18:49
  • 7
    $\begingroup$ 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. $\endgroup$
    – John Bentin
    Commented Mar 30, 2012 at 21:24
  • 4
    $\begingroup$ How does this nonsense answer have anything to do with the OP? $\endgroup$
    – user641
    Commented Mar 31, 2012 at 18:19
  • 4
    $\begingroup$ 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. $\endgroup$
    – guy
    Commented Apr 1, 2012 at 20:18

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .