mersenneforum.org Fermat ECM
 Register FAQ Search Today's Posts Mark Forums Read

 2017-12-12, 11:32 #1 houding     "Adolf" Nov 2013 South Africa 61 Posts Fermat ECM Just more of a curiosity. I have 4 computers doing ECM on Fermat numbers. Usually they are assigned F21 or F22 ECM work. The one now was assigned F18. Any reason?
2017-12-13, 03:25   #2
petrw1
1976 Toyota Corona years forever!

"Wayne"
Nov 2006

32·5·103 Posts

Quote:
 Originally Posted by houding Just more of a curiosity. I have 4 computers doing ECM on Fermat numbers. Usually they are assigned F21 or F22 ECM work. The one now was assigned F18. Any reason?
That seems to be typical. I get the same.

It seems the server likes to mix up your workload a bit based on the amount of RAM you have on your user preferences.

If you give it a lot less (maybe about 200 or 300M) you will get assignments more in the F12-F15 range but on the other hand this little RAM will slow down the processing.

 2017-12-13, 08:22 #3 LaurV Romulan Interpreter     Jun 2011 Thailand 100100111001012 Posts Note that the "chain" is "inclusive", in the sense that when you test for a factor of F22, you also test for factors of the smaller F21, F20, etc. That is because $$F_{n+1}=(F_n-1)^2+1$$ and to test if some q divides $$F_n$$, you repeatedly square 2 and test if it is -1 (mod q). You can fall on -1 earlier than n iterations, therefore finding a factor for a smaller Fermat number. All factors are $$q=k*2^{n+2}+1$$ so factors of larger F will "fit" for smaller F too with a larger k (double, quadruple, 8 times, etc). So, technically, if you look for a factor of F22, you may find a factor of F21, or F18, etc, "accidentally". For example, you want to see if 641 is a factor of F7 (this is a stupid example, as 641 is 640+1=5*128+1=5*2^7+1, so it can only be a factor to F5 maximum (5=7-2), even if we would not know anything about it, we would not test it if it is a factor of F7, but well, it will suffice for the current example). Then we would have to square 2 (mod 641) a number of 7 times, to see if 2^2^7 is -1. Code: gp > a=Mod(2,641) Mod(2, 641) gp > a=a^2 Mod(4, 641) gp > a=a^2 Mod(16, 641) gp > a=a^2 Mod(256, 641) gp > a=a^2 Mod(154, 641) gp > a=a^2 Mod(640, 641) gp > Right now we got -1 at the fifth iteration, so we just found a factor of F5, even if we were looking for a factor of F7. A better example would be, assume we want to check if 2424833 is a factor of F14. This can be a factor of F14, because 2424833 =37*2^16+1 the power of 2 is at least 16=14+2. So: Code: gp > q=37*2^16+1 2424833 gp > a=Mod(2,q) Mod(2, 2424833) gp > a=a^2 Mod(4, 2424833) gp > a=a^2 Mod(16, 2424833) gp > a=a^2 Mod(256, 2424833) gp > a=a^2 Mod(65536, 2424833) gp > a=a^2 Mod(588053, 2424833) gp > a=a^2 Mod(896679, 2424833) gp > a=a^2 Mod(2253235, 2424833) gp > a=a^2 Mod(1126485, 2424833) gp > a=a^2 Mod(2424832, 2424833) gp > Then here we stop because we got -1, after 9 steps, which means that 2^2^9=-1 (mod q), or, adding 1 in both sides, F9 is 0 (mod q), which means we just found out that 2424833 is a factor of F9, even if we were looking for a factor of F14. Which can be written as 2424833 = 37*2^16+1 = (37*2^5)*2^11+1 = 1184 * 2^11 + 1, a "good" factor of F9 for k=1184. It is as simple as that. Last fiddled with by LaurV on 2017-12-13 at 08:29

 Similar Threads Thread Thread Starter Forum Replies Last Post houding FermatSearch 1 2016-12-02 12:36 MattcAnderson Factoring 40 2015-04-08 08:08 ATH Operazione Doppi Mersennes 2 2015-01-25 06:27 ET_ Factoring 21 2010-03-15 21:02 Crook Math 5 2005-05-05 17:18

All times are UTC. The time now is 15:48.

Thu May 13 15:48:28 UTC 2021 up 35 days, 10:29, 2 users, load averages: 2.52, 2.09, 2.09