Thread: Faster Factoring Algorithm? View Single Post
2007-02-22, 09:04   #2
xilman
Bamboozled!

"πΊππ·π·π­"
May 2003
Down not across

11,027 Posts

Quote:
 Originally Posted by Citrix What do you think, does there exist a faster factoring algorithm, than current methods? When do you think humanity will find it (Year)? Just looking for some thoughts from the experts. Thanks!
I'll take this question in the spirit I think it was asked in. That is, I'll indulge in vigorous hand-waving and give my gut feelings. Note that I do not consider myself an expert.

Personally, I think there is a reasonable chance that there is a deterministic polynomial time factoring algorithm which runs on Turing machines.

Some of the reasons for this optimism.

An expected polynomial time algorithm exists for quantum Turing machines.

Factoring is easily proved to be in NP --- hint, multiplication is in P

Although a P-time algorithm hasn't yet been found, neither has factoring been shown not to be in P, despite a lot of effort in each direction.

Forty years ago, only exp-time algorithms were known. Then came a bunch of algorithms (CFRAC, QS, ECM and others) which in a well-defined sense are half-way between polynomial and exponential time. Then came an algorithm (NFS) which, in the same sense, is one third of the way from polynomial to exponential time. Progress towards a P-time algorithm has been made --- indeed, we are already two thirds of the way to the destination.

Analysis of an exponential-time algorithm, Pollard's rho, shows that it works by computing highly composite integers. Unfortunately, the number of factors of those integers isn't large enough for Pollard-rho to factor in P-time.

If we could calculate x! mod N in polynomial time it could be used to produce a P-time factoring algorithm. Once more, no such algorithm has been found yet neither has it been proved that an algorithm can not exist. x!, of course, is a highly composite integer.

I make no prediction as to when a P-time algorithm may be discovered, assuming one exists. It may be years ago (though I doubt it) or it may be decades or centuries hence. It's quite possible, in my opinion, that it may not be discovered by a human mathematician.

Paul