Join PrimeGrid
Returning Participants
Community
Leader Boards
Results
Other
drummerslowrise

Message boards :
Fermat Divisor Search :
Divisors of "small" Fermat numbers
Author 
Message 
BurVolunteer tester
Send message
Joined: 25 Feb 20 Posts: 395 ID: 1241833 Credit: 149,711,705 RAC: 948,026

While it's proven that Fermat numbers F5 to F32 are composite, only F5 to F11 are fully factored.
The unknown factors of F12 will have a small n of 14...1x, but k is consequently very large, so the search is tedious.
Fermatsearch organizes the search for factors and apparently people are testing with very large k. 7595155767819149 * 2^105+1 has been found in december to be a factor of F110, but I wonder how large k  or k's  will be for F12.
The remaining cofactor of F12 has more than 1000 digits, so with n being on the order of 10^1, k can potentially be huge, with hundreds of digits. And while primality testing of k*2^12+1 is fast, even with large k, the probability to be a factor is wellknown to be 1/k, so a lot of very small primes will have to be found, billions or more.
I know this is a bit out of the scope of PG, since no large primes are to be found here and I'm not sure if there is even software that supports k in the range of 10^20 or so, but I think it's an interesting project. Has anyone here ever worked on it?
I find it intriguing that even though the primes are so small and proving their primality is easy, finding one that actually factors F12 is so hard.
____________
Primes: 1281979 & 12+8+1979 & 1+2+8+1+9+7+9 & 1^2+2^2+8^2+1^2+9^2+7^2+9^2 & 12*8+19*79 & 12^81979 & 1281979 + 4 (cousin prime)  


The remaining cofactor of F12 has more than 1000 digits, so with n being on the order of 10^1, k can potentially be huge, with hundreds of digits. And while primality testing of k*2^12+1 is fast, even with large k, the probability to be a factor is wellknown to be 1/k, so a lot of very small primes will have to be found, billions or more.
True. So the remaining factors of F12 cannot be found by considering the form k*2^n + 1 where n is 14, 15, 16, etc. This worked fine for the initial factors (Pervushin in 1877; Western in 1903 (two factors)). Clearly, it is not practical when the k can have hundreds of digits, as you say.
The most recent factor of F12 from 2010 was:
17353230210429594579133099699123162989482444520899*2^15 + 1
= 568630647535356955169033410940867804839360742060818433
In its thread on Mersenneforum you can see that it was found with the elliptic curve method for factoriation (ECM). It was not found the way we do in PrimeGrid, by first stumbling upon the prime, and then checking if it happened to divide any Fermat number.
So progress with F12 must come from better techniques for factorizing numbers.
Maybe you can ask at Mersenneforum.org.
/JeppeSN  

Yves GallotVolunteer developer Project scientist Send message
Joined: 19 Aug 12 Posts: 669 ID: 164101 Credit: 305,042,960 RAC: 0

Ryan Propper found a 83digit prime factor of 7^{337} + 1 with ECM.
Since F_{12} is a main target, the smallest unknown factor should have more than 80 digits.
SNFS is able to factor some numbers of the form a^{b} +/ 1 with 350 digits. The remaining cofactor of F_{12} is still too large for this method.
For "small" Fermat numbers, the best method is to try to factor them with ECM. The current status is available here.  


Ryan Propper found a 83digit prime factor of 7^{337} + 1 with ECM.
Since F_{12} is a main target, the smallest unknown factor should have more than 80 digits.
SNFS is able to factor some numbers of the form a^{b} +/ 1 with 350 digits. The remaining cofactor of F_{12} is still too large for this method.
For "small" Fermat numbers, the best method is to try to factor them with ECM. The current status is available here.
Very interesting. Looking at the table in your link, it looks like F12 (n=4096) still needs many curves in the column Digits in factor=65. So I wonder how certain it is that the smallest unknown factor has more than 80 digits, as you say.
Of course it is likely that some people do attempts on F12 without reporting to PrimeNet.
/JeppeSN  

Yves GallotVolunteer developer Project scientist Send message
Joined: 19 Aug 12 Posts: 669 ID: 164101 Credit: 305,042,960 RAC: 0

Of course it is likely that some people do attempts on F12 without reporting to PrimeNet.
F_{12} = 65536^{256} + 1 which is a GFN8. A GPU can quickly test thousands of curves simultanously using a NTT for the products modulo F_{12}.
My argument is that the largest prime factors found with ECM have more than 80 digits and that F_{12} is the most wanted... but I might be wrong.
 


that F_{12} is the most wanted...
I want to submit A046052(12), please. /JeppeSN  

Ravi FernandoProject administrator Volunteer tester Project scientist Send message
Joined: 21 Mar 19 Posts: 157 ID: 1108183 Credit: 9,334,510 RAC: 4,853

My argument is that the largest prime factors found with ECM have more than 80 digits and that F_{12} is the most wanted... but I might be wrong.
I'm not an expert on ECM, but I do know that it's possible to find an unexpectedly large factor by luck. According to Ryan himself (mersenneforum post 1, 2), that was the case with his record: he ran about 5000 curves, whereas one would expect to need about 10000 to find even a 65digit factor.  

BurVolunteer tester
Send message
Joined: 25 Feb 20 Posts: 395 ID: 1241833 Credit: 149,711,705 RAC: 948,026

I forgot that large k's are not just a software limitation problem, but since k > 2^n in those cases, ECM or APR have to be used. My thought was that a good CPU would just create a large list of suitable primes and even with 1/k probability for being a factor it would be a viable attempt. But without Proth that won't work.
It was not found the way we do in PrimeGrid, by first stumbling upon the prime, and then checking if it happened to divide any Fermat number. Interesting, I thought ECM was solely a primality test. But apparently it's been developed for factorization? So does it prove primality by proving there are no factors other than N?
So progress with F12 must come from better techniques for factorizing numbers. I guess many people would be very interested in such techniques...
____________
Primes: 1281979 & 12+8+1979 & 1+2+8+1+9+7+9 & 1^2+2^2+8^2+1^2+9^2+7^2+9^2 & 12*8+19*79 & 12^81979 & 1281979 + 4 (cousin prime)  

Ravi FernandoProject administrator Volunteer tester Project scientist Send message
Joined: 21 Mar 19 Posts: 157 ID: 1108183 Credit: 9,334,510 RAC: 4,853

Interesting, I thought ECM was solely a primality test. But apparently it's been developed for factorization? So does it prove primality by proving there are no factors other than N?
You're confusing ECM with ECPP. ECPP (elliptic curve primality proving) is a method for proving the primality of a number (up to a few tens of thousands of digits) which is already known to be a PRP. ECM (elliptic curve method) is a method for finding small factors (up to several tens of digits) of numbers that are known to be composite. Both use the group law of an elliptic curve, but they do different things with it.  


Interesting, I thought ECM was solely a primality test. But apparently it's been developed for factorization?
ECM and ECPP are not synonymous. In 1985 came
1. ellipticcurve factorization method (ECM)
by Hendrik Lenstra. Based on that, a method for primality testing, namely
2. elliptic curve primality proving (ECPP)
was developed.
So these are different concepts. But they are related, because ECPP is based on ECM.
/JeppeSN
EDIT: Oh, Ravi already explained that :)  

Yves GallotVolunteer developer Project scientist Send message
Joined: 19 Aug 12 Posts: 669 ID: 164101 Credit: 305,042,960 RAC: 0

My argument is that the largest prime factors found with ECM have more than 80 digits and that F_{12} is the most wanted... but I might be wrong.
I'm not an expert on ECM, but I do know that it's possible to find an unexpectedly large factor by luck. According to Ryan himself (mersenneforum post 1, 2), that was the case with his record: he ran about 5000 curves, whereas one would expect to need about 10000 to find even a 65digit factor.
For a fixed set of parameters and a fixed prime size, the likelihood of success per curve is constant. Then ECM is a Bernoulli trial and if p is small the cumulative exponential distribution is a good approximation.
According to GMPECM table, the expected number of curves for a 83digit prime factor was about 2400k.
1  exp(5k/2400k) ~ 0.2%.
Note that it was in 2012 and the program is not optimized for a specific form of numbers. Arithmetic modulo F_{12} with fast transforms should be five or ten times faster than the "28prime NTT" of GMPECM.
Then the current range for recent computers should be about a 80/90 digits.  

Post to thread
Message boards :
Fermat Divisor Search :
Divisors of "small" Fermat numbers 