mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2007-02-22, 03:28   #1
Citrix
 
Citrix's Avatar
 
Jun 2003

1,553 Posts
Default 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!
Citrix is offline   Reply With Quote
Old 2007-02-22, 09:04   #2
xilman
Bamboozled!
 
xilman's Avatar
 
May 2003
Down not across

276116 Posts
Default

Quote:
Originally Posted by Citrix View Post
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
xilman is offline   Reply With Quote
Old 2007-02-22, 16:26   #3
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101×103 Posts

100000000100112 Posts
Default

As a tag-along 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?
Uncwilly is offline   Reply With Quote
Old 2007-02-22, 20:22   #4
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

22·881 Posts
Default

Quote:
Originally Posted by xilman View Post
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.
Hans Riesel also thought so, and mentioned this idea in one of his books. When I pointed this out in sci.crypt back in 1998, Bob said the idea was 'unconvincing'. Nothing has happened recently that gives anyone reason to change that view, unless you can take the AKS primality test as cause for hope that hard problems in number theory are susceptible to solution using simple tools.

jasonp
jasonp is offline   Reply With Quote
Old 2007-02-22, 20:32   #5
xilman
Bamboozled!
 
xilman's Avatar
 
May 2003
Down not across

17·593 Posts
Default

Quote:
Originally Posted by jasonp View Post
Hans Riesel also thought so, and mentioned this idea in one of his books. When I pointed this out in sci.crypt back in 1998, Bob said the idea was 'unconvincing'. Nothing has happened recently that gives anyone reason to change that view, unless you can take the AKS primality test as cause for hope that hard problems in number theory are susceptible to solution using simple tools.

jasonp
Knuth mentioned it long before Riesel (I've read it in each of their books). I got it from Knuth and the observation was probably old before he wrote TAOCP Vol 2.

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
xilman is offline   Reply With Quote
Old 2007-09-18, 20:41   #6
wwelling81
 

23×3×137 Posts
Default

is O(ln) fast?
  Reply With Quote
Old 2007-12-23, 11:36   #7
mgb
 
"Michael"
Aug 2006
Usually at home

24·5 Posts
Default

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
mgb is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Faster factoring with binary splitting? __HRB__ Software 3 2009-01-03 16:27
Shor's Factoring Algorithm - does it even work? Citrix Factoring 37 2008-08-16 14:19
Prime Factoring Algorithm Visu Math 66 2008-05-12 13:55
A new prime factoring algorithm? Visu Factoring 22 2006-11-09 10:43
faster factoring? S80780 Lone Mersenne Hunters 10 2003-04-08 21:51

All times are UTC. The time now is 09:11.

Thu Jul 9 09:11:24 UTC 2020 up 106 days, 6:44, 0 users, load averages: 1.83, 1.51, 1.48

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.