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
    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.2012-03-30
  • 0
    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.2012-03-30
  • 1
    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.2012-03-30
  • 0
    The fundamental theorem of arithmetic says that every number is a product of primes. So just pick your favourite way of describing huge numbers…2012-03-30
  • 10
    Tell me more of this "Fundamental Theorem" of which you speak. Just kidding, yes of course I meant exactly two primes. Thanks.2012-03-30
  • 0
    There are many tests which can tell whether a number is prime without giving prime factors for composites. So I don't see any *a priori* reason why there shouldn't be a test that tells you if there are exactly 2 prime factors without telling you what they are.2012-03-30
  • 0
    (+1) following the edit. Also, there are some things that God cannot do ... :)2012-03-30
  • 0
    When I read the title I thought: I just wish I would know everything Hardy could or could not do, cause then I would probably be as smart as him :)2012-04-01
  • 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 ?

  • 0
    I like the idea. But by the same token, we can say that the two prime factors of that number are 2 iff Goldbach is true for N < 10^{10^{99999}} else 3, and 7 iff Goldbach is true for N < 10^{10^{99999}} else 5.2012-03-30
  • 4
    As someone had pointed out before this answer was deleted earlier, this does not exhibit a number, it exhibits a function.2012-03-30
  • 2
    @Graphth: That statement makes no sense. (Aside: if you meant a nullary function, then I suppose it would make sense. But it's clear that every integer-valued nullary function uniquely defines an integer, and vice versa)2012-03-30
  • 1
    @Hurkyl: OP is asking if there is an algorithm which, given a number, can efficiently tell if that number is the product of two primes. This answers "counter-example" is an algorithm (function) which outputs a number based on whether Goldbach is true for some large $N$. I hope you can see why this is not really a counter-example: OP did not ask for an algorithm to determine whether another algorithm outputs the product of two primes *(it is trivial to show that would be [uncomputable](http://en.wikipedia.org/wiki/Halting_problem))*.2012-03-30
  • 2
    @BlueRaja: It's one thing to assert that the presentation (of a number) used in this answer is not of a form the OP was looking for. It's another thing entirely to claim that it's not a number!2012-03-30
  • 4
    This is not exhibiting a number. This is exhibiting a function whose value you cannot compute with current means of mathematics.2012-03-30
  • 0
    Yes, there's that comment I saw earlier. I knew it started with an A but I forgot who it was.2012-03-30
  • 7
    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.2012-03-30
  • 0
    @John: The function is from the collection of FOL models of PA into $\{14,15\}$. The function is defined to be $f(N)=14$ if $N\models\text{Goldbach's conjecture}$ and $f(N)=15$ otherwise. The current problem is that we do not know how to compute this function, whether or not it is constant (i.e. is the conjecture provable from PA), for this reason I **cannot** explicitly say what is the exact set of this function as a subset of $\{N\mid N\models{\sf PA}\}\times\{14,15\}$.2012-03-30
  • 2
    @AsafKaragila We know how to compute this. 10^10^9999 is a finite number. N is not a variable. The statement is 'every even integer less then 10^10^9999 is the sum of two primes.'2012-03-31
  • 3
    @dfggfdg: Can you please compute the Ramsey numbers or Busy Beaver of numbers greater than 6? Oh, you can't? I suppose that means those are infinite... wait, a finite graph can have infinitely many edges or vertices? Hooray! We found the contradiction in mathematics, now we can write a paper and put everyone out of a job.2012-03-31
  • 0
    @AsafKaragila "Goldbach is true for N" is meant to mean "N is a sum of two primes". Now clarified.2012-03-31
  • 0
    @Asaf: We can view $1$ as choice function on the class of FOL models of PA. That's no reason to stop calling $1$ a number. That's what you're doing with the number cited in the answer. Even if we replace his condition with some other formula of PA that defines an element of $\mathbb{N}$ whose precise value is undecidable in PA, it's still a formula of PA that defines an element of $\mathbb{N}$.2012-03-31
  • 3
    @Hurkyl: What are you talking about? $1$ is a well defined symbol in PA. The original answer was "14 if the Goldbach conjecture is true, 15 if false." In a specific model, sure. But what if the Goldbach conjecture is true if and only if there are no nonstandard primes? Of course that would mean it is independent of PA, but how can you tell **internally** whether or not there are nonstandard primes in your universe?2012-03-31
  • 4
    How does this nonsense answer have anything to do with the OP?2012-03-31
  • 3
    @AsafKaragila and confused Steve. The original was "14 if Goldbach is true for N<10^10^9999", its true that your misintepretations of my answer dont have anything to do with the OP.2012-04-01
  • 4
    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.2012-04-01
  • 2
    @Asaf: Semantics are irrelevant. We have a unary predicate in the language of number theory which FOL proves (we don't even need the axioms of PA!) is satisfied by a unique natural number, and thus yields a well-defined natural number. Insisting that it is a function is an exercise in wordplay, not mathematics. It simply *doesn't matter* how this number gets interpreted into models... unless (going back to the spirit of the answer) by 'exhibit' you mean something more restrictive than simply providing a definition. (the version in the answer even has the same 'value' in all models!)2012-04-02
  • 3
    @dfggfdg Actually, Asaf's statement of your original answer is correct. The thing is, your answer was deleted. I'm not sure if you did it or if a moderator did it, but it was in the form Asaf said before it was deleted. Then, you reanswered (not sure if it's the same account or a different one, as you went through 3 different names at least in the process... I saw Banned, Moderator, and now dfggfdg). So, the edit history does not show the original answer, but Asaf is still correct. The main point is, this answer obviously doesn't answer the OPs question.2012-04-02
  • 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.

  • 0
    I think the question requires a constructive proof - yours seems to need you to have the number to be tested already in hand.2012-03-30
  • 0
    *"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.2012-03-30
  • 0
    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.2012-03-30
  • 6
    @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.2012-03-30
  • 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
    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.2012-04-04
  • 0
    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.2012-04-04
  • 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.

  • 2
    "Semiprime." Aha, "[interesting semiprimes](http://primes.utm.edu/glossary/page.php?sort=Semiprime)".2012-03-30
  • 0
    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...2012-04-01
  • 0
    What is NFS?...2012-04-01
  • 0
    @leo: The Number Field Sieve, the asymptotically-fastest known method for factoring large numbers.2012-04-01
  • 0
    @Charles, thanks for the clarification2012-04-02