tag:blogger.com,1999:blog-3722233.post1217723546605282423..comments2021-04-20T09:52:56.297-05:00Comments on Computational Complexity: Did YOU think the NSA could factor fast?Lance Fortnowhttp://www.blogger.com/profile/06752030912874378610noreply@blogger.comBlogger12125tag:blogger.com,1999:blog-3722233.post-42178096049334018502013-09-21T22:54:35.443-05:002013-09-21T22:54:35.443-05:00Most likely 1, 2, 3, 4 (a variation), and 6. I bel...Most 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.<br /><br />Also, I would recommend everyone to re-watch South Park episode "Mystery of the Urinal Deuce."Ahttps://www.blogger.com/profile/02715495667566510040noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-79437543915527823122013-09-18T10:46:14.813-05:002013-09-18T10:46:14.813-05:00I think factoring is in P and NSA knows a better w...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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-59426834749419395112013-09-17T15:57:48.527-05:002013-09-17T15:57:48.527-05:00Well, that's the point. If they sat down and s...Well, 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.Anonymoushttps://www.blogger.com/profile/09364120444779754928noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-13538443809114177542013-09-17T06:08:38.311-05:002013-09-17T06:08:38.311-05:00Terry Tao has remarked that attractive logical puz...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 … <b><a href="http://terrytao.wordpress.com/2011/04/07/the-blue-eyed-islanders-puzzle-repost/#comment-245322" rel="nofollow">The Blue-eyed Islanders Puzzle</a></b> is among the most celebrated examples of a mathematical puzzle that is difficult partly because it is scary. <br /><br />Cognitive 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 <b><a href="http://www.huffingtonpost.com/marty-kaplan/most-depressing-brain-fin_b_3932273.html" rel="nofollow">motivated numeracy</a>.</b><br /><br />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?<br /><br />It is similarly difficult for us to contemplate these scary questions, as it is for Terry Tao's islanders to contemplate the scary story: <i>“A trusted foreigner comes and says ‘I see a blue-eyed person.’”</i>John Sidleshttps://www.blogger.com/profile/16286860374431298556noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-54105304961012317692013-09-17T02:12:32.210-05:002013-09-17T02:12:32.210-05:00Would not 4 be a crime against humanity ?
Hiding ...Would not 4 be a crime against humanity ? <br />Hiding new maths that could mean a giant step for maths and sciences, thus progresses that would benefit to mankind ?Anonymoushttps://www.blogger.com/profile/12005749767583527357noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-86813609803290883932013-09-16T20:04:00.722-05:002013-09-16T20:04:00.722-05:00As a historical note relating to factoring, Gödel&...As a historical note relating to factoring, <b><a href="http://rjlipton.wordpress.com/the-gdel-letter/" rel="nofollow">Gödel's celebrated 1956 letter to von Neumann</a></b> includes this prescient passage:<br /><br />-----------------<br />"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."<br />-----------------<br /><br />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.John Sidleshttps://www.blogger.com/profile/16286860374431298556noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-29631549493362153282013-09-16T17:49:30.581-05:002013-09-16T17:49:30.581-05:00I agree with Anonymous : Let's say the NSA is ...I 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 scaleAnonymoushttps://www.blogger.com/profile/09360810877910199189noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-85119638442898604612013-09-16T17:30:24.460-05:002013-09-16T17:30:24.460-05:00> Maybe sociology since the government has cen...> Maybe sociology since the government has census data and other data that is not available to the public.<br /><br />The 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.<br /><br />Except, if you take NSA spying the whole worlds internet traffic. This might include MUCH more social information than Facebook does.Martin Thomahttps://www.blogger.com/profile/13629221699214248094noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-19510310539151342922013-09-16T16:58:30.916-05:002013-09-16T16:58:30.916-05:00FACTOR_X_FOR_X_LESS_THAN_Y may be doable, but it c...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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-8037638699108283652013-09-16T15:54:16.175-05:002013-09-16T15:54:16.175-05:00My reasoning is that since they are doing the trap...My reasoning is that since they are doing the trapdoor stuff<br />they are focusing their energies on ways to crack codes<br />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. <br /><br />But to say the truth is `closer to 1' should probably be ammended to `closer to 1 than I thought'.GASARCHhttps://www.blogger.com/profile/06134382469361359081noreply@blogger.comtag:blogger.com,1999:blog-3722233.post-45119662943250532762013-09-16T15:38:10.760-05:002013-09-16T15:38:10.760-05:00On what do you base your conclusions? What we lear...On 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. <br /><br />We 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. Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-3722233.post-59426055061615375882013-09-16T15:24:21.462-05:002013-09-16T15:24:21.462-05:00Option 7. NSA has tables of all prime numbers up t...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. <br /><br /><br />Anonymousnoreply@blogger.com