20171212, 11:32  #1 
"Adolf"
Nov 2013
South Africa
75_{8} 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? 
20171213, 03:25  #2  
1976 Toyota Corona years forever!
"Wayne"
Nov 2006
Saskatchewan, Canada
4537_{10} Posts 
Quote:
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 F12F15 range but on the other hand this little RAM will slow down the processing. 

20171213, 08:22  #3 
Romulan Interpreter
Jun 2011
Thailand
2×3×5^{2}×61 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_n1)^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=72), 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 > 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 > It is as simple as that. Last fiddled with by LaurV on 20171213 at 08:29 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
GMPFermat  houding  FermatSearch  1  20161202 12:36 
GMPFermat for Windows  MattcAnderson  Factoring  40  20150408 08:08 
P1/P+1 on Fermat numbers  ATH  Operazione Doppi Mersennes  2  20150125 06:27 
New Fermat factor!  ET_  Factoring  21  20100315 21:02 
Fermat's Theorem  Crook  Math  5  20050505 17:18 