mersenneforum.org  

Go Back   mersenneforum.org > Math Stuff > Analysis & Analytic Number Theory

Reply
 
Thread Tools
Old 2021-02-06, 16:44   #1
bgbeuning
 
Dec 2014

3×5×17 Posts
Default 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,
bgbeuning is offline   Reply With Quote
Old 2021-02-06, 20:55   #2
bgbeuning
 
Dec 2014

111111112 Posts
Default

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.
bgbeuning is offline   Reply With Quote
Old 2021-02-07, 09:23   #3
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

22·3·11·83 Posts
Default

Quote:
Originally Posted by bgbeuning View Post
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
xilman is offline   Reply With Quote
Reply

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 2021-01-29 21:17
Generalized Fermat numbers (in our case primes) pepi37 Conjectures 'R Us 4 2015-10-09 14:49
Best case Fermat Factors yourskadhir Miscellaneous Math 5 2012-12-12 04:18
Modification of Fermat's method rdotson Miscellaneous Math 0 2007-07-27 10:32
Fermat's factoring method with Gauss's inprovement Carlos Programming 0 2005-09-11 12:50

All times are UTC. The time now is 23:30.


Fri Oct 22 23:30:26 UTC 2021 up 91 days, 17:59, 0 users, load averages: 1.16, 1.63, 1.45

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.