Hacker News Reader

Comment by Jabbles | Hacker News Reader

Let's say a serious attempt consists of several months of work by an expert, someone who knows enough number theory to read the literature on this problem. Then the number of people who have seriously tried must be on the order of magnitude of 100.

In academia, maybe. But I would not be surprised if millenia of experts' time has been spent on this problem in intelligence agencies.

View on HN

I think that number (100) is a bit too low. There are students, graduates, post-grad fellows, and otherwise thousands of people living and breathing number theory. Sure, they might not directly stare at a blackboard with The Problem of Factoring staring back at them, but they are very much doing that indirectly.

Just like the AKS primality testing algorithm depends on clever number theory, any progress, any new trick would be very likely reported, and we'd see it in charts like these:

https://aiimpacts.org/progress-in-general-purpose-factoring/

I think the core point of the OP you are missing is that he doesn't consider people indirectly, tangentially working on related things as doing "serious" work on factoring.

I tend to agree. Look at Fermat's last theorem: it went over a century as one of mathematics hardest unsolved problems, and in reality all it took was one guy dedicating a couple of months of exclusive work to it. Factoring (and discrete log?) is probably similar.

I work in this field as a non-academically-trained cryptographer. Cryptographers prefer to assume their assumed-hard functions are in fact hard and move on. Especially those that have academic training--they supposedly know better than to waste their time on such a hard problem.. but by induction that means approximately nobody is really looking at it.

> it went over a century as one of mathematics hardest unsolved problems, and in reality all it took was one guy dedicating a couple of months of exclusive work to it.

Six years, not a couple of months.

There were plenty of people who tackled this problem and who failed to make any headway. {Edit: I phrased this last sentence really clumsily, sorry.}

> There were plenty of people who tackled this problem and who failed to make any headway.

There was also plenty of meaningful progress throughout the 20th century at least, showing that the FLT was implied by other statements which would be easier to prove. Wiles's work was a follow-on to this progress; it's quite misleading to say that it "took" a single guy working over six years to prove FLT.

Also Andrew Wiles' six years of focused worked fundamentally depended on very deep work that Ken Ribet had just completed, which in turn relied on decades of highly nontrivial work by Mazur, Katz, and others on modular curves and modular forms, which made surprising connections with other areas of mathematics. Finally, Wiles' first announced proof of FLT was wrong, and Richard Taylor collaborated with him to find a correct and quite different proof. (Disclaimer: I published a book on modular forms, and cowrote papers with some of the people mentioned above.)

I'm going to read your book, because your book with Mazur on the Riemann Hypothesis was incredible.

Free PDF: https://wstein.org/books/modform/

Thanks.

By his own report, it was a few months of tackling the problem from various angles until he found the pathway that would eventually bear fruit, and formalizing that and fixing little problems along the way was what the next six years were spent on.

He was the lucky one. Many many mathematicians thought they saw a path. And spent years. And it did not lead anywhere/there in the end.

See also the many P = NP proof attempts. (Sure, most of them are complete crackpot garbage, but that doesn't mean serious attempts are not made, and probably more serious attempts are made that then go nowhere so the author doesn't disclose it.)

in reality all it took was one guy dedicating a couple of months of exclusive work to it

This is wrong. Many professional mathematicians attacked the problem, and many useful discoveries were made before it was proved. For a brief summary, see https://en.wikipedia.org/wiki/Fermat%27s_Last_Theorem#Early_...

But if intelligence agencies broke factoring, would we know? Maybe they have.

Unlikely, as they wouldn’t keep using methods that they’ve broken themselves

I doubt it, too; but using methods you've broken, but know others haven't, is a great way to convince people you haven't broken it either. And if you suspect they have, it's a great channel for misinformation.

You could also embed content with stronger security inside the wrapper you’ve broken, so even if someone else has figured it out, they can’t decrypt your real messages.

Hopefully.

Nice

They could switch algorithms and claim that they were just doing it to be resistant against quantum computers.

That's not the case. With compartmentalization as a core organizational design, the people with the crack won't be saying anything to the operations and infrastructure folks.

A key portion of an advantage like this would be who to share 1) derived intel and 2) capability with.

If they have then they are using it exceedingly sparingly.

I strongly suspect it would be impossible to use it to any moderate degree without being found out in one way or another.

I know this is a very very poorly worded question :) but I wonder what the most amazing secret was that was held for the longest time?

Probably the most useful thing to do with this power if you had it would be and signing your exploits with all sorts of legit keys. Maximal effective exposed area on all parts of the hardware and software stack of multiple potential opponents. The real work would be using the information and trying to find other ways to discover the same thing. Classic intel problem.

We know they had public key crypto a few years before RSA.

> but I wonder what the most amazing secret was that was held for the longest time?

Very relevant, probably the Allie's breaking the Axis enigma code in WWII.

https://en.m.wikipedia.org/wiki/Ultra

If the NSA broke RSA, they'd have a similar program set up to ensure nobody notices.

>I wonder what the most amazing secret was that was held for the longest time?

I heard that the use of the golden ratio in projects such as the engineering of cathedrals, required that the first thing you do before you draw your plan is to draw a pentagram, in order to derive the ratio using simple drawing tools, and then carefully erase it, or in other words, make it occult. http://www.matematicasvisuales.com/english/html/geometry/gol...

Also, I'd really like to know who in the hell built the Ankythera device. https://en.wikipedia.org/wiki/Antikythera_mechanism

Reply on news.ycombinator.com