## Other

drummers-lowrise

Message boards : Fermat Divisor Search : Divisors of "small" Fermat numbers

Author Message
Bur
Volunteer tester

Joined: 25 Feb 20
Posts: 459
ID: 1241833
Credit: 278,511,688
RAC: 700,734

Message 147861 - Posted: 25 Jan 2021 | 18:54:44 UTC

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 co-factor 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 well-known 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.
____________
1281979 * 2^485014 + 1 is prime ... no further hits up to: n = 4,800,000

JeppeSN

Joined: 5 Apr 14
Posts: 1532
ID: 306875
Credit: 35,595,467
RAC: 10,416

Message 147869 - Posted: 25 Jan 2021 | 23:11:22 UTC - in response to Message 147861.

The remaining co-factor 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 well-known 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 Gallot
Volunteer developer
Project scientist

Joined: 19 Aug 12
Posts: 672
ID: 164101
Credit: 305,042,960
RAC: 0

Message 147878 - Posted: 26 Jan 2021 | 9:03:08 UTC

Ryan Propper found a 83-digit prime factor of 7337 + 1 with ECM.
Since F12 is a main target, the smallest unknown factor should have more than 80 digits.
SNFS is able to factor some numbers of the form ab +/- 1 with 350 digits. The remaining co-factor of F12 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.

JeppeSN

Joined: 5 Apr 14
Posts: 1532
ID: 306875
Credit: 35,595,467
RAC: 10,416

Message 147893 - Posted: 26 Jan 2021 | 16:16:12 UTC - in response to Message 147878.

Ryan Propper found a 83-digit prime factor of 7337 + 1 with ECM.
Since F12 is a main target, the smallest unknown factor should have more than 80 digits.
SNFS is able to factor some numbers of the form ab +/- 1 with 350 digits. The remaining co-factor of F12 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 Gallot
Volunteer developer
Project scientist

Joined: 19 Aug 12
Posts: 672
ID: 164101
Credit: 305,042,960
RAC: 0

Message 147895 - Posted: 26 Jan 2021 | 17:12:20 UTC - in response to Message 147893.

Of course it is likely that some people do attempts on F12 without reporting to PrimeNet.

F12 = 65536256 + 1 which is a GFN-8. A GPU can quickly test thousands of curves simultanously using a NTT for the products modulo F12.
My argument is that the largest prime factors found with ECM have more than 80 digits and that F12 is the most wanted... but I might be wrong.

JeppeSN

Joined: 5 Apr 14
Posts: 1532
ID: 306875
Credit: 35,595,467
RAC: 10,416

Message 147900 - Posted: 26 Jan 2021 | 17:45:52 UTC - in response to Message 147895.

that F12 is the most wanted...

I want to submit A046052(12), please. /JeppeSN

Ravi Fernando
Volunteer tester
Project scientist

Joined: 21 Mar 19
Posts: 175
ID: 1108183
Credit: 10,184,126
RAC: 4,978

Message 147901 - Posted: 26 Jan 2021 | 18:00:30 UTC - in response to Message 147895.

My argument is that the largest prime factors found with ECM have more than 80 digits and that F12 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 65-digit factor.

Bur
Volunteer tester

Joined: 25 Feb 20
Posts: 459
ID: 1241833
Credit: 278,511,688
RAC: 700,734

Message 147902 - Posted: 26 Jan 2021 | 18:13:12 UTC

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...
____________
1281979 * 2^485014 + 1 is prime ... no further hits up to: n = 4,800,000

Ravi Fernando
Volunteer tester
Project scientist

Joined: 21 Mar 19
Posts: 175
ID: 1108183
Credit: 10,184,126
RAC: 4,978

Message 147905 - Posted: 26 Jan 2021 | 18:53:36 UTC - in response to Message 147902.

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.

JeppeSN

Joined: 5 Apr 14
Posts: 1532
ID: 306875
Credit: 35,595,467
RAC: 10,416

Message 147907 - Posted: 26 Jan 2021 | 19:01:59 UTC - in response to Message 147902.

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. elliptic-curve 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 Gallot
Volunteer developer
Project scientist

Joined: 19 Aug 12
Posts: 672
ID: 164101
Credit: 305,042,960
RAC: 0

Message 147932 - Posted: 27 Jan 2021 | 13:21:27 UTC - in response to Message 147901.

My argument is that the largest prime factors found with ECM have more than 80 digits and that F12 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 65-digit 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 GMP-ECM table, the expected number of curves for a 83-digit 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 F12 with fast transforms should be five or ten times faster than the "28-prime NTT" of GMP-ECM.
Then the current range for recent computers should be about a 80/90 digits.

Message boards : Fermat Divisor Search : Divisors of "small" Fermat numbers