Fermat ECM

[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?

[petrw1]

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.

[LaurV]

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.

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:

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.