Re: A factoring algorithm

Phil Carmody wrote:
> daw@taverner.cs.berkeley.edu (David Wagner) writes:
> > Phil Carmody wrote:
> > >"Pubkeybreaker" <Robert_silverman@raytheon.com> writes:
> > >> The world does not need another O(N^1/4) algorithm.
> > >
> > >It also doesn't need knee-jerk gainsayers.
> > >
> > >If you'd like to get some stuff of your chest, did the world
> > >need Dixon's algorithm? Or Lehman's? Anyone more recent that
> > >you'd like to condescendingly trash at the same time, while
> > >you're at it?
> >
> > I'm with Bob. At the time, yes, the world needed Dixon's algorithm,
> > both because it had some new ideas and an interesting runtime. But as
> > for right now? Nope, the world wouldn't need another Dixon's algorithm,
> > and it wouldn't need another O(N^1/4) algorithm, unless it had some very
> > interesting new ideas.
> >
> > In other words, what was novel 50 years ago is not the same as what
> > is novel today. And the state of the art in factoring is not the same
> > today as it once was.
>
> Can you conceive of the possibility that one of the more
> talented and experienced minds in the field could examine
> a novel O(n^(1/4)) algorithm, and recognise something that
> has been missed by the amateur who originated the algorithm,
> and by doing so reduce its complexity in a significant way?
>
> If not, then you're insulting the experienced minds in the
> field as much as the OP.
>
> Of course, the only way to get someone experienced in the
> field to have a look at the algorithm is to make it public.
> I wouldn't expect any effort to be expended by said experts
> before then. Their precious time can also be saved by _not_
> wasting it writing knee-jerk dismissals.

Maybe you would like to insult Eric Bach while you are at it?

"The world does not need another O(N^1/4) algorithm" is something
Eric said to me back in the 90's at a conference. He too had invented
a
new O(N^1/4) algorithm based upon ideas from Schroeppel's linear list
sieve.
His comment was that his work wasn't worth publishing because the world
did not need another exponential time algorithm.

At the time Pollard Rho, Squfof, and Lehman's algorithms became
public, (early 70's) the best algorithms were CFRAC, and trial
division. The new
algorithms were substantial improvments on the latter.

The art has advanced considerably since then. We don't need to
reinvent a
square wheel.
Received on Tue Jan 17 16:49:18 2006