We have very good reasons to think that Factoring is NOT NP-complete. As for P--- much murkier. People have tried to get it into P because of crypto and have not succeeded, hence many people think that Factoring is NOT in P. But there is so much math there that perhaps could be exploited to show it IS in P. Another very odd possibility is that it is KNOWN to be in P but only by the NSA. Crytpo has had this before- where some concepts were known to governments before they were known to the public, even the academic public.
I will need to revise that now. BEFORE the recent revelations there were
the following points of view on factoring:
- The NSA cannot factor any better than what is known in the literature. Maybe a bit better because they use more parallelism.
- The NSA has taken the known algorithms and found the right parameters and has special purpose hardware so can do them better than anyone else, but nothing of interest mathematically. Perhaps some very interesting subtle points of math and hardware. What they have would not get into STOC/FOCS/CRYPTO (though maybe it should- that's another debate). This is the one I believed.
- The NSA has an algorithm that is better than the literature (e.g., exponential in (log n)^{1/5}). But not in P. This would surely get into STOC/FOCS/CRYPTO and win a prize.
- The NSA has factoring in P through some very interesting and new mathematics. If this was public then perhaps a Turing Award. Some serious number theorists do think that Factoring IS in P, so this one is not quite so implausible.
- The NSA has a quantum computer that factors quickly. I do not now of anyone serious who believed this. Of course, this could be a case of the No True Scotsman Paradox--- if someone really believed this I would (perhaps unfairly) declare them non-serious.
- The NSA does not have a better algorithm, but has managed to put trapdoors in stuff so that they and only they could break certain codes.(A covert version of Clipper Chip.) So they can break codes but not in a way that is interesting mathematically.
The truth seems to be that the truth is between 1 and 2, closer to 1, and also item 6.
In particular, the NSA does not seem that much ahead of academics.
In the past governments were way ahead of academics in crypto. This no longer seems to be the case (at least in America). I speculate that this is because there is now a large community of people doing research in crypto openly, publishing openly, so the government is no longer the only (or almost the only) game in town. Also, many non-government industries use crypto and some do research in it. This also helps the NSA- they can use results in the open literature, but they can't get that much ahead of it.
Are there other fields where the government is ahead of academics and industry? On a guess stuff with weapons and weapon detection, since not many academics work on that. Maybe sociology since the government has census data and other data that is not available to the public.
Option 7. NSA has tables of all prime numbers up to N for very large values of N. In fact values so large that their mere storage presents a challenge (let alone computing them). They have been collecting said tables since at least the late 1970s.
ReplyDeleteOn what do you base your conclusions? What we learned was that the NSA had certain unspecified abilities to break particular encryption methods on a wide scale, likely through backdoors and tricks like #6.
ReplyDeleteWe did not learn that they do not have any particular ability. Why do you say the truth is closest to 1? I don't see how we know more about this than before.
My reasoning is that since they are doing the trapdoor stuff
Deletethey are focusing their energies on ways to crack codes
that are not interesting mathematically. Also we know more about what they do because of Snowden and none of it seems to be really really cool mathematics.
But to say the truth is `closer to 1' should probably be ammended to `closer to 1 than I thought'.
FACTOR_X_FOR_X_LESS_THAN_Y may be doable, but it could still be expensive enough that putting in the trapdoors saves a lot of money.
DeleteI agree with Anonymous : Let's say the NSA is able to factor one or two 1024 random semi-primes per day. This would be closer to 3 since it would definitely make it to CRYPTO if it were a public result but that's clearly not enough for them to decrypt most of the internet traffic. Putting backdoors in common software/hardware makes things much easier to scale
DeleteWell, that's the point. If they sat down and saw that without a major breakthrough, using backdoors is better, why bother with attempting the major breakthrough? The NSA is interesting in the results, not the mathematics, after all.
Delete> Maybe sociology since the government has census data and other data that is not available to the public.
ReplyDeleteThe industry has Facebook. I guess 1,000,000,000+ people giving away their data voluntarily beats 300,000,000+ people having to contribute to census.
Except, if you take NSA spying the whole worlds internet traffic. This might include MUCH more social information than Facebook does.
As a historical note relating to factoring, Gödel's celebrated 1956 letter to von Neumann includes this prescient passage:
ReplyDelete-----------------
"It would be interesting to know, for instance, the situation concerning the determination of primality of a number and how strongly in general the number of steps in finite combinatorial problems can be reduced with respect to simple exhaustive search."
-----------------
However, Gödel's letter is *mainly* worth reading (as it seems to me) as an example of warm humanity and affection that is communicated through the medium of mathematics.
Would not 4 be a crime against humanity ?
ReplyDeleteHiding new maths that could mean a giant step for maths and sciences, thus progresses that would benefit to mankind ?
Terry Tao has remarked that attractive logical puzzles require "resolving apparent contradictions [that] requires very clear thinking about the nature of knowledge." That is why simple-to-state yet celebrated-for-difficulty logical puzzles commonly incorporate elements that are socially transgressive or even terrifying … The Blue-eyed Islanders Puzzle is among the most celebrated examples of a mathematical puzzle that is difficult partly because it is scary.
ReplyDeleteCognitive science shows us — plainly yet distressingly — that in contemplating such puzzles, greater mathematical aptitude can be anti-correlated with the ability to reach correct inferences: this is the counterintuitive phenomenon of motivated numeracy.
Cryptography is fascinating because (historically) it has been a playground of motivated numeracy — "our Enigma ciphers are invulnerable!" — and so at the back of our minds we worry that perhaps our most cherished postulates may be motivatively biased. Is factoring really hard? Are quantum computers really feasible? Are quantum dynamical systems really hard-to-simulate? Does the entire edifice of complexity theory really rest upon secure postulates and axioms?
It is similarly difficult for us to contemplate these scary questions, as it is for Terry Tao's islanders to contemplate the scary story: “A trusted foreigner comes and says ‘I see a blue-eyed person.’”
I think factoring is in P and NSA knows a better way of factoring than the rest. They might not factor as such, but they might be able to form a pool of plausible primes for a given number and try all of the combinations within that pool.
ReplyDeleteMost likely 1, 2, 3, 4 (a variation), and 6. I believe, it depends on how much value the encrypted stuff is to them. They have (had) some sharp guys.
ReplyDeleteAlso, I would recommend everyone to re-watch South Park episode "Mystery of the Urinal Deuce."