View Single Post
Old 2007-02-22, 20:32   #5
xilman's Avatar
May 2003
Down not across

245338 Posts

Originally Posted by jasonp View Post
Hans Riesel also thought so, and mentioned this idea in one of his books. When I pointed this out in sci.crypt back in 1998, Bob said the idea was 'unconvincing'. Nothing has happened recently that gives anyone reason to change that view, unless you can take the AKS primality test as cause for hope that hard problems in number theory are susceptible to solution using simple tools.

Knuth mentioned it long before Riesel (I've read it in each of their books). I got it from Knuth and the observation was probably old before he wrote TAOCP Vol 2.

Thanks for reminding me of AKS. That is indeed additional grounds for optimism.

Primality testing went from being as hard as factoring, to slightly superpolynomial to expected polynomial to deterministic polynomial over the course of a few decades. I'm optimistic that it can be brought back to being as hard as factoring again.

Bob and I discussed the very same question about difficulty of factoring and prospects of improvement when we met last September. I suspect that I'm a bit more optimistic than he is, but he'll have to make his own comments on that score.

We've certainly each thought about possible algorithmic improvements, in quite different ways, but neither of us has got anywhere. That last should be obvious --- you would have heard from one of us if we had!

xilman is offline   Reply With Quote