Thread: Fermat ECM View Single Post
 2017-12-13, 08:22 #3 LaurV Romulan Interpreter     Jun 2011 Thailand 100100101011102 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