View Single Post
Old 2021-02-07, 09:23   #3
xilman's Avatar
May 2003
Down not across

1157210 Posts

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, and then scroll down to "Multiplier improvement". Finally read and understand Ref. 1 ---

Last fiddled with by xilman on 2021-02-07 at 09:24
xilman is offline   Reply With Quote