Re: A factoring algorithm

David Wagner wrote:
> Phil Carmody wrote:
> >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?
>
> Of course it's conceivable that a talented and experienced mind could look
> at the O(N^1/4) algorithm and come up with some fast factoring algorithm.
> But as far as I can see, it's just as conceivable that a talented and
> experienced mind could find a fast factoring algorithm without wasting
> their time on this algorithm. Unless there is some reason to spend time
> reading the O(N^1/4) algorithm -- time that would, I suspect, be better
> spent on other things -- why would anyone bother?
>
> If the proposer of the algorithm has some reason to think that this is
> interesting and has promise to lead to a faster factoring algorithm, then
> I hope he will explain. But lacking that, and if Bob Silverman doesn't
> see anything interesting here, well, I know whose word I will trust.
>
> Note that the burden on the proposer to understand the prior work
> and to make the case that their scheme has some interesting features
> over and above what has been done before. If they don't, well, they
> will be ignored. You might think that is not fair, but that is how
> the system works. (And it works that way for a very good reason: no
> one has unlimited time, and so we have to prioritize. If the proposer
> cannot coherently explain why it is worth my time to study his system,
> then 99% of the time that means that it is indeed not worth my time.)

I am not alone in my view. I quoted Eric Bach as having a similar view
in
another post.

SQUFOF is an O(N^1/4) algorithm. It improves to O(N^1/5) if GRH is
true.
[the reason for the dependency of GRH is that GRH limits the number of
*succcessive* quadratic non-residues that can appear in the continue
fraction
expansion of sqrt(N)].

The implied constants in the O() estimates are quite small for this
algorithm
[i.e. close to 1; I have measured them] AND the algorithm requires
only
half-length arithmetic.

Despite this, a well tuned version of QS is FASTER than SQUFOF even
for
numbers as small as 52 to 53 bits [I have measured this as well].

SQUFOF is quite a bit faster in practice than Pollard Rho [Pollard Rho
requires
double length arithmetic].

P-1, when implemented with convolutions in stage 2 is another O(N^1/4)
method.

Another O(N^1/4) method is not going to improve the art in any way.

It also seems that people are criticizing this viewpoint because the
new algorithm
might present new mathematical ideas. However, I tend to be quite
precise in
my use of language. I never said that new mathematical ideas are not
welcome.
I said that another exponential time algorithm is not needed. Yet
people seem to
infer that in saying the latter, I mean the former.

Several years ago, I invented a new algorithm that I showed to Ron
Rivest. It
was based on a different idea: It was a recursive descent algorithm
that solved
the more general equation N = ab + a + b. At each stage it had to
solve two
auxiliary equations related to the first equation. The key feature
was that N
could be proved to *decrease* by at least 1 bit at each iteration.
The problem was
that in actual performance the method was quite slow. Indeed, a rough
probabilistic
analysis showed that the average case was close to the worst case. And
the worst
case requires a full traversal of a binary tree of depth log(N)/2,
i.e. an exponential
algorithm. I never bothered to publish because another exponential
algorithm would
have been pointless, and amortization algorithms were not new either.
Received on Tue Jan 17 16:49:41 2006