Re: A factoring algorithm

From: daw@xxxxxxxxxxxxxxxxxxxxxxxx (David Wagner)
Date: Mon, 9 Jan 2006 23:00:01 +0000 (UTC)

>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.
.

Follow-Ups:
- Re: A factoring algorithm
  - From: wbhart

References:
- A factoring algorithm
  - From: hart_wb
- Re: A factoring algorithm
  - From: Pubkeybreaker
- Re: A factoring algorithm
  - From: wbhart

Prev by Date: Re: Computing big numbers
Next by Date: Re: self-appointed expert? {Re: RS-232 random number generator}
Previous by thread: Re: A factoring algorithm
Next by thread: Re: A factoring algorithm
Index(es):
- Date
- Thread

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 ... >>of arithmetic operations ... Involves factorials of numbers or something IIRC. ...
(sci.crypt)
Re: Selection-Sort in C
... solving that problem is the cost of the best algorithms. ... making is to assume that all sorting algorithms are comparison sorts. ... Thetawhere n is the number of bits in the data set. ...
(comp.lang.c)
Re: Theoretical Problems
... people use algorithms for finding least cost travelling ... I have been in many parts of the IT industry (including ... people in commerce and industry actually care that much about least cost ... Linear optimization and piece-wise linear convex minimization are very ...
(sci.math)