Re: A factoring algorithm

>Many algorithms have never seen the light of day because they are not better
>than the current best algorithms at the time. For example, Lenstra once told
>me about an algorithm which would factor any number in a polynomial number
>of arithmetic operations

FYI, that one is in the literature. If you're referring to what I think,
that was published (over two decades ago, I think) and if I recall
correctly it is due to Adi Shamir. I can probably dig up a citation if
you like.

The catch is that the size of the numbers becomes exponentially big,
and consequently the cost, measured in bit operations, is exponential.
Received on Tue Jan 17 16:49:24 2006