mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > PrimeNet

Reply
 
Thread Tools
Old 2017-12-12, 11:32   #1
houding
 
houding's Avatar
 
"Adolf"
Nov 2013
South Africa

3D16 Posts
Default 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?
houding is offline   Reply With Quote
Old 2017-12-13, 03:25   #2
petrw1
1976 Toyota Corona years forever!
 
petrw1's Avatar
 
"Wayne"
Nov 2006
Saskatchewan, Canada

32·7·71 Posts
Default

Quote:
Originally Posted by houding View Post
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.
petrw1 is offline   Reply With Quote
Old 2017-12-13, 08:22   #3
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

8,963 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
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
GMP-Fermat houding FermatSearch 1 2016-12-02 12:36
GMP-Fermat for Windows MattcAnderson Factoring 40 2015-04-08 08:08
P-1/P+1 on Fermat numbers ATH Operazione Doppi Mersennes 2 2015-01-25 06:27
New Fermat factor! ET_ Factoring 21 2010-03-15 21:02
Fermat's Theorem Crook Math 5 2005-05-05 17:18

All times are UTC. The time now is 08:02.

Sat Dec 5 08:02:44 UTC 2020 up 2 days, 4:14, 0 users, load averages: 3.21, 2.57, 2.09

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.