20070222, 03:28  #1 
Jun 2003
631_{16} Posts 
Faster Factoring Algorithm?
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! 
20070222, 09:04  #2  
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
3^{2}·5^{2}·7^{2} Posts 
Quote:
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 Ptime 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 exptime algorithms were known. Then came a bunch of algorithms (CFRAC, QS, ECM and others) which in a welldefined sense are halfway 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 Ptime algorithm has been made  indeed, we are already two thirds of the way to the destination. Analysis of an exponentialtime 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 Pollardrho to factor in Ptime. If we could calculate x! mod N in polynomial time it could be used to produce a Ptime 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 Ptime 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 

20070222, 16:26  #3 
6809 > 6502
"""""""""""""""""""
Aug 2003
101Γ103 Posts
10115_{10} Posts 
As a tagalong to the main question:
Is there a faster or better method that is known, but is awaiting some breakthrough in computers before it can become practical? Quantum machines can right? 
20070222, 20:22  #4  
Tribal Bullet
Oct 2004
3×1,181 Posts 
Quote:
jasonp 

20070222, 20:32  #5  
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
3^{2}×5^{2}×7^{2} Posts 
Quote:
Thanks for reminding me of AKS. That is indeed additional grounds for optimism. Primality testing went from being as hard as factoring, to slightly superpolynomial to expected polynomial to deterministic polynomial over the course of a few decades. I'm optimistic that it can be brought back to being as hard as factoring again. Bob and I discussed the very same question about difficulty of factoring and prospects of improvement when we met last September. I suspect that I'm a bit more optimistic than he is, but he'll have to make his own comments on that score. We've certainly each thought about possible algorithmic improvements, in quite different ways, but neither of us has got anywhere. That last should be obvious  you would have heard from one of us if we had! Paul 

20070918, 20:41  #6 
8050_{10} Posts 
is O(ln) fast?

20071223, 11:36  #7 
"Michael"
Aug 2006
Usually at home
2·41 Posts 
Notions versus notations!* Personally I think it may need a new development in mathematics as radical as congruence theory or the advent of complex numbers. Then factoring might be routine.
*Gauss 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Faster factoring with binary splitting?  __HRB__  Software  3  20090103 16:27 
Shor's Factoring Algorithm  does it even work?  Citrix  Factoring  37  20080816 14:19 
Prime Factoring Algorithm  Visu  Math  66  20080512 13:55 
A new prime factoring algorithm?  Visu  Factoring  22  20061109 10:43 
faster factoring?  S80780  Lone Mersenne Hunters  10  20030408 21:51 