mersenneforum.org Fermat method best case
 Register FAQ Search Today's Posts Mark Forums Read

 2021-02-06, 16:44 #1 bgbeuning   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,
 2021-02-06, 20:55 #2 bgbeuning   Dec 2014 111111112 Posts Learning about NP-complete problems was a while a go, but "which factorization is closest to sqrt(N)" sounds like the "0-1 knapsack" problem.
2021-02-07, 09:23   #3
xilman
Bamboozled!

"๐บ๐๐ท๐ท๐ญ"
May 2003
Down not across

2·3·5·379 Posts

Quote:
 Originally Posted by bgbeuning 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,
https://en.wikipedia.org/wiki/Fermat...ization_method and then scroll down to "Multiplier improvement". Finally read and understand Ref. 1 --- https://www.ams.org/journals/mcom/19...-0340163-2.pdf

Last fiddled with by xilman on 2021-02-07 at 09:24

 Similar Threads Thread Thread Starter Forum Replies Last Post EdH Other Mathematical Topics 52 2021-01-29 21:17 pepi37 Conjectures 'R Us 4 2015-10-09 14:49 yourskadhir Miscellaneous Math 5 2012-12-12 04:18 rdotson Miscellaneous Math 0 2007-07-27 10:32 Carlos Programming 0 2005-09-11 12:50

All times are UTC. The time now is 06:10.

Wed Jun 29 06:10:27 UTC 2022 up 76 days, 4:11, 1 user, load averages: 0.91, 1.11, 1.08