Re: A factoring algorithm

"David Wagner" <daw@taverner.cs.berkeley.edu> wrote in message
news:dpupth$24rp$2@agate.berkeley.edu...
> >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,

yep. Involves factorials of numbers or something IIRC.

> and consequently the cost, measured in bit operations, is exponential.

Thanks, I can find it on mathscinet. I hadn't realised it had been
published. Sheesh, the things they published back then!

Bill.
Received on Tue Jan 17 16:49:25 2006