Thread: Fermat ECM
View Single Post
Old 2017-12-13, 08:22   #3
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

212548 Posts
Default

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
LaurV is offline   Reply With Quote