mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2019-10-16, 11:34   #12
ThiloHarich
 
ThiloHarich's Avatar
 
Nov 2005

101 Posts
Default

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.

Last fiddled with by ThiloHarich on 2019-10-16 at 12:09
ThiloHarich is offline   Reply With Quote
Old 2019-10-16, 13:44   #13
xilman
Bamboozled!
 
xilman's Avatar
 
"π’‰Ίπ’ŒŒπ’‡·π’†·π’€­"
May 2003
Down not across

101001111001102 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
Old 2019-10-16, 13:53   #14
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

31×113 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.
Ideas like this are how I was able to get 'a' to 10^14 in an hour. But as Xilman said, this would only work if the (presumably 100 digit) factors shared their leading 43 digits.
bsquared is offline   Reply With Quote
Old 2019-10-16, 14:31   #15
ThiloHarich
 
ThiloHarich's Avatar
 
Nov 2005

101 Posts
Default

Quote:
Originally Posted by firstexceed View Post
Thank you BSQUARED. He suggested to take the squareroot of it as starting point and work downwards (upwards) from there.
I was referring to this hint. Of coarse Fermat works only if both factors were really close.

Ahh you check 10^14 a = sqrt(n) + a' in the area sqrt(n) in 1 hour -> quite impressive.

Last fiddled with by ThiloHarich on 2019-10-16 at 14:45
ThiloHarich is offline   Reply With Quote
Old 2019-10-16, 15:58   #16
chris2be8
 
chris2be8's Avatar
 
Sep 2009

206710 Posts
Default

Quote:
Originally Posted by SnakeMan View Post
I can assure you, "The Creator" was *very* aware of how difficult this would be!
Are you the creator? If not how do you know?

Chris
chris2be8 is offline   Reply With Quote
Old 2019-10-17, 03:39   #17
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

32×1,061 Posts
Default

Quote:
Originally Posted by Dylan14 View Post
That graph is quite old and it should be somehow interpreted like "CoresHoursGHz" instead of the "CPU Hours", because the new CPUs have many cores which are much faster than at the time the tables were drawn. But beside of that, the graphs are still amazingly accurate. For example it says that you need about 5000 "CPU Hours" to factor a C160. This may look like a freaking long-LONG time, considering that my wheelbarrow can crunch a C160 in about 5-6 days.

However, there will be 10 cores used for it, each running at 4 GHz, and it also has 4 (four) fast memory channels (x99 i7-6950x), and a LOT of cache memory, compared to other CPUs, which gives it about 20-30% more speed when HT is used (20 threads). Therefore, ~5.5 days times 24 hours, times 10 cores, times 4 GHz, is about 5280 "CPU Hours", more or less...

So,... yeah...

Edit: @OP, I edited first post of the thread to put the long number in code tags. Please use code tags for long lines without breaks - such long lines make the thread very difficult to read on narrow screens because the size of the browser is extended out of the screen.

Edit 2: related to the puzzle itself (we just clicked the link), is there any way to exploit the "terrain difficulty" and "additional hint"? You have the most significant part of the coordinates, which puts you in a "about" 100km large square, and you are looking for something situated on easy terrain (not a mountain, for example), on the south east face (so, it has faces/sides!) at few feet up (so, it has an "up", or "uphill", or is something "floating" above the ground, etc). I have no idea where the place is, and no time for digging deep, I also never participated in the challenge, and I may be talking stupidities, but maybe a perspicacious person could squeeze in the box without factoring the C200? There is also the observation they made that there may be more than 2 factors, so it may be deliberate to point to ECM.

Last fiddled with by LaurV on 2019-10-17 at 04:02
LaurV is offline   Reply With Quote
Old 2019-10-17, 12:57   #18
PFPoitras
 
"Patrick Poitras"
Oct 2019

2·33 Posts
Default

At the risk of running this thread off-topic, that graph is really good, and I'd like to read more about the methodology behind it.
PFPoitras is offline   Reply With Quote
Old 2019-10-18, 03:52   #19
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

32·1,061 Posts
Default

We did about 10^10 rho iterations with few random bases each, with x^2-1. Came back empty. So, it is "solid" from this pov.
LaurV is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
OpenCL GPU P-1 Factoring and ECM Factoring xx005fs GPU Computing 3 2018-10-27 14:49

All times are UTC. The time now is 19:32.


Thu Jun 24 19:32:33 UTC 2021 up 27 days, 17:19, 1 user, load averages: 1.16, 1.36, 1.55

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.