mersenneforum.org factoring a c200
 Register FAQ Search Today's Posts Mark Forums Read

 2019-10-16, 11:34 #12 ThiloHarich     Nov 2005 101 Posts 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
2019-10-16, 13:44   #13
xilman
Bamboozled!

"πΊππ·π·π­"
May 2003
Down not across

247468 Posts

Quote:
 Originally Posted by ThiloHarich 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.

2019-10-16, 13:53   #14
bsquared

"Ben"
Feb 2007

31·113 Posts

Quote:
 Originally Posted by ThiloHarich 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.

2019-10-16, 14:31   #15
ThiloHarich

Nov 2005

101 Posts

Quote:
 Originally Posted by firstexceed 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

2019-10-16, 15:58   #16
chris2be8

Sep 2009

1000000100102 Posts

Quote:
 Originally Posted by SnakeMan 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

2019-10-17, 03:39   #17
LaurV
Romulan Interpreter

Jun 2011
Thailand

9,547 Posts

Quote:
 Originally Posted by Dylan14
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

 2019-10-17, 12:57 #18 PFPoitras   "Patrick Poitras" Oct 2019 5410 Posts 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.
 2019-10-18, 03:52 #19 LaurV Romulan Interpreter     Jun 2011 Thailand 9,547 Posts 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.