mersenneforum.org (https://www.mersenneforum.org/index.php)
-   Factoring (https://www.mersenneforum.org/forumdisplay.php?f=19)
-   -   factoring a c200 (https://www.mersenneforum.org/showthread.php?t=24846)

 ThiloHarich 2019-10-16 11:34

There are some improvements to Fermat's method.
See [url]https://en.wikipedia.org/wiki/Fermat%27s_factorization_method[/url] -> 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.

 xilman 2019-10-16 13:44

[QUOTE=ThiloHarich;528128]There are some improvements to Fermat's method.
See [url]https://en.wikipedia.org/wiki/Fermat%27s_factorization_method[/url] -> 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.[/QUOTE]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.

 bsquared 2019-10-16 13:53

[QUOTE=ThiloHarich;528128]There are some improvements to Fermat's method.
See [url]https://en.wikipedia.org/wiki/Fermat%27s_factorization_method[/url] -> Sieve improvement.[/QUOTE]

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.

 ThiloHarich 2019-10-16 14:31

[QUOTE=firstexceed;528051]Thank you BSQUARED. He suggested to take the squareroot of it as starting point and work downwards (upwards) from there. [/QUOTE]

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.

 chris2be8 2019-10-16 15:58

[QUOTE=SnakeMan;528056]I can assure you, "The Creator" was *very* aware of how difficult this would be![/QUOTE]

Are you the creator? If not how do you know?

Chris

 LaurV 2019-10-17 03:39

[QUOTE=Dylan14;528048][URL="https://stdkmd.net/nrr/graph/gnfs_time.png"]This graph gives [/URL]...[/QUOTE]
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... :picard:

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.

 PFPoitras 2019-10-17 12:57

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.

 LaurV 2019-10-18 03:52

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.

All times are UTC. The time now is 09:42.