20210206, 16:44  #1 
Dec 2014
3×5×17 Posts 
Fermat method best case
I am a computer guy and not a math guy.
I have been playing with Fermat's factoring method and come upon a math question. In the worst case Fermat is O(n^1/2) but in the best case it is O(1). I am looking for ways to make the best case more common. If we multiply 1000 small consecutive primes together to make N, how long does Fermat's method take to factor N? Since N has 1000 factors, there are 2^1000 different ways to factor N. Another way to ask the same question is, which factorization is closest to sqrt(N) and how far from sqrt(N) is it? Maybe a math person will find this interesting. If not, that is OK too. Thanks, 
20210206, 20:55  #2 
Dec 2014
3·5·17 Posts 
Learning about NPcomplete problems was a while a go,
but "which factorization is closest to sqrt(N)" sounds like the "01 knapsack" problem. 
20210207, 09:23  #3  
Bamboozled!
"πΊππ·π·π"
May 2003
Down not across
2^{2}·7·383 Posts 
Quote:
Last fiddled with by xilman on 20210207 at 09:24 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Help with series convergence in Fermat method of factoring  EdH  Other Mathematical Topics  52  20210129 21:17 
Generalized Fermat numbers (in our case primes)  pepi37  Conjectures 'R Us  4  20151009 14:49 
Best case Fermat Factors  yourskadhir  Miscellaneous Math  5  20121212 04:18 
Modification of Fermat's method  rdotson  Miscellaneous Math  0  20070727 10:32 
Fermat's factoring method with Gauss's inprovement  Carlos  Programming  0  20050911 12:50 