Hacker News Reader

Comment by primecommenter | Hacker News Reader

While perhaps not an advance, the algorithms implemented are state-of-the-art (GNFS, Pollard's p-1 test, Williams' p+1 test, cyclotomic polynomial test). But whatever the running times, it is an astounding artifact.

View on HN

There is a year or two of work on top of the documentation I have included. Also, I think it is likely that there are some incremental improvements to the existing algorithms that my uncle put in place without necessarily documenting. Whilst these might not be theoretically interesting, their combined effect could be significant. There may also be some new maths in there too, as he was undoubtedly a brilliant mathematician.

Do you have any kind of bio on him? Even a picture?

I'm hoping to get both of these. It needs some collaboration with my family to do it properly.

It's remarkable that we refer to algorithms invented as "late" as the 90's as state-of-the-art. But sadly, it is so.

Even more remarkable is that they build directly upon the 400-year-old method of Fermat (http://en.wikipedia.org/wiki/Fermat%27s_factorization_method).

Well, directly is a bit of a stretch. It's probably more fair to say they're directly based off the Powers-Lehmer-Morrison-Brilhart (also Kraitchik, for the discrete log) method, which introduced the concept of factor bases and combining relations to find a difference of squares.

The officially published ones. It remains an open question what the NSA knows.

I was going to back up the idea that the NSA might potentially be ahead of the public community of number theorists and cryptographers by citing the relative sizes of the two groups. Unfortunately, those numbers are classified. :(

The NSA recently stated that they are only a couple of years ahead. And by that I take it they mean their computers are bigger. Recall that they are a military outfit. Only a small part of what they do is crypto related. Despite them having 40,000 employees or so, one shouldn't read that as meaning they have 40,000 people working on breaking RSA. They do many other things.

Reply on news.ycombinator.com