- **PrimeNet**
(*https://www.mersenneforum.org/forumdisplay.php?f=11*)

- - **Fermat ECM**
(*https://www.mersenneforum.org/showthread.php?t=22783*)

Fermat ECMJust 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? |

[QUOTE=houding;473807]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?[/QUOTE] 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. |

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 >[/CODE]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 [U]can[/U] 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 >[/CODE]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 [U]is[/U] as simple as that. |

All times are UTC. The time now is 20:29. |

Powered by vBulletin® Version 3.8.11

Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.