Re: A factoring algorithm


"David Wagner" <daw@xxxxxxxxxxxxxxxxxxxxxxxx> wrote in message
news:dpupth$24rp$2@xxxxxxxxxxxxxxxxxxxxx
> >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.


.

Relevant Pages

  • Re: New 2 Cryptography
    ... Newsgroups: sci.crypt ... > cryptography and I thought I'd post here to ask a few questions. ... Also there is a question of licensing one or more algorithms, ... rounds of arithmetic operations, and you wind up with something that would ...
    (sci.crypt)
  • Re: Optimization
    ... >> performance characteristics when run on a 20 year old and a new computer. ... old textbooks contain estimates of the relative costs of + and /. ... of arithmetic operations is almost irrelevant. ... constant prefactor in the performance of most algorithms. ...
    (sci.math.num-analysis)
  • Re: A factoring algorithm
    ... >than the current best algorithms at the time. ... For example, Lenstra once told ... >of arithmetic operations ... and consequently the cost, measured in bit operations, is exponential. ...
    (sci.crypt)
  • Re: Hash components
    ... Where can i download the IIRC Hagen's "Delphi Encryption Library"? ... > Lohan Spies wrote: ... >> and crc algorithms i am interested in. ... > you will get a fair share of support questions from end users just by ...
    (borland.public.delphi.thirdpartytools.general)
  • Re: Supercomputing: An Industry in Need of a Revolution
    ... See what happens when you use bad algorithms on poorly designed computers? ... (Sorry, Robert M, couldn't resist.) ... I did put IIRC in. ...
    (comp.arch)