View Single Post
Old 2019-10-16, 13:44   #13
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

2·3·13·137 Posts
Default

Quote:
Originally Posted by ThiloHarich View Post
There are some improvements to Fermat's method.
See https://en.wikipedia.org/wiki/Fermat...ization_method -> Sieve improvement.
You can really cut down the candidates to check by applying a modulo argument. For primes this argument can be applied multiple times.
For each mod prime number argument it halves the number of numbers "x" to check.
The product of the first 52 primes is ~ 10^98.
Since you can not store or iterate efficiently over all the possible candidates you can not do this for the first 52 primes, you might only seedup by using the first - lets say 8 - primes which gives a speedup of 2^8 = 256.

Also checking if the number is a square can be speed up by applying a mod argument.
Doing it for a power of 2 filters out most of the number to check.
All this is true but mostly irrelevant in practice. Fermat only finds factors if they are *very* close together. Most people don't care whether a computation takes a trillion years or only a billion years to complete.
xilman is offline   Reply With Quote