PrimeGrid
Please visit donation page to help the project cover running costs for this month

Toggle Menu

Join PrimeGrid

Returning Participants

Community

Leader Boards

Results

Other

drummers-lowrise

Advanced search

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

Author Message
Profile BurProject donor
Volunteer tester
Avatar
Send message
Joined: 25 Feb 20
Posts: 474
ID: 1241833
Credit: 313,509,766
RAC: 996,712
321 LLR Ruby: Earned 2,000,000 credits (2,092,823)Cullen LLR Ruby: Earned 2,000,000 credits (2,315,295)ESP LLR Amethyst: Earned 1,000,000 credits (1,445,099)Generalized Cullen/Woodall LLR Ruby: Earned 2,000,000 credits (2,330,027)PPS LLR Ruby: Earned 2,000,000 credits (2,025,505)PSP LLR Ruby: Earned 2,000,000 credits (2,064,832)SoB LLR Amethyst: Earned 1,000,000 credits (1,669,219)SR5 LLR Ruby: Earned 2,000,000 credits (2,065,004)SGS LLR Ruby: Earned 2,000,000 credits (2,027,649)TRP LLR Ruby: Earned 2,000,000 credits (2,089,856)Woodall LLR Ruby: Earned 2,000,000 credits (2,112,258)321 Sieve (suspended) Ruby: Earned 2,000,000 credits (2,107,153)PPS Sieve Turquoise: Earned 5,000,000 credits (5,096,952)AP 26/27 Turquoise: Earned 5,000,000 credits (5,150,782)GFN Turquoise: Earned 5,000,000 credits (7,510,843)WW Double Silver: Earned 200,000,000 credits (270,420,000)PSA Amethyst: Earned 1,000,000 credits (1,022,470)
Message 147861 - Posted: 25 Jan 2021 | 18:54:44 UTC
Last modified: 25 Jan 2021 | 18:55:18 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 = 5,000,000

Profile JeppeSNProject donor
Avatar
Send message
Joined: 5 Apr 14
Posts: 1549
ID: 306875
Credit: 35,940,187
RAC: 10,456
Found 1 prime in the 2020 Tour de Primes321 LLR Gold: Earned 500,000 credits (529,293)Cullen LLR Gold: Earned 500,000 credits (611,298)ESP LLR Silver: Earned 100,000 credits (174,818)Generalized Cullen/Woodall LLR Bronze: Earned 10,000 credits (85,939)PPS LLR Jade: Earned 10,000,000 credits (13,422,871)PSP LLR Silver: Earned 100,000 credits (428,457)SoB LLR Silver: Earned 100,000 credits (466,812)SR5 LLR Silver: Earned 100,000 credits (145,419)SGS LLR Silver: Earned 100,000 credits (112,277)TRP LLR Silver: Earned 100,000 credits (342,501)Woodall LLR Silver: Earned 100,000 credits (109,455)321 Sieve (suspended) Silver: Earned 100,000 credits (175,037)PPS Sieve Bronze: Earned 10,000 credits (10,113)AP 26/27 Bronze: Earned 10,000 credits (12,129)GFN Ruby: Earned 2,000,000 credits (2,059,478)WW Turquoise: Earned 5,000,000 credits (9,640,000)PSA Turquoise: Earned 5,000,000 credits (7,614,290)
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
Send message
Joined: 19 Aug 12
Posts: 673
ID: 164101
Credit: 305,042,960
RAC: 0
GFN Double Silver: Earned 200,000,000 credits (305,042,960)
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.

Profile JeppeSNProject donor
Avatar
Send message
Joined: 5 Apr 14
Posts: 1549
ID: 306875
Credit: 35,940,187
RAC: 10,456
Found 1 prime in the 2020 Tour de Primes321 LLR Gold: Earned 500,000 credits (529,293)Cullen LLR Gold: Earned 500,000 credits (611,298)ESP LLR Silver: Earned 100,000 credits (174,818)Generalized Cullen/Woodall LLR Bronze: Earned 10,000 credits (85,939)PPS LLR Jade: Earned 10,000,000 credits (13,422,871)PSP LLR Silver: Earned 100,000 credits (428,457)SoB LLR Silver: Earned 100,000 credits (466,812)SR5 LLR Silver: Earned 100,000 credits (145,419)SGS LLR Silver: Earned 100,000 credits (112,277)TRP LLR Silver: Earned 100,000 credits (342,501)Woodall LLR Silver: Earned 100,000 credits (109,455)321 Sieve (suspended) Silver: Earned 100,000 credits (175,037)PPS Sieve Bronze: Earned 10,000 credits (10,113)AP 26/27 Bronze: Earned 10,000 credits (12,129)GFN Ruby: Earned 2,000,000 credits (2,059,478)WW Turquoise: Earned 5,000,000 credits (9,640,000)PSA Turquoise: Earned 5,000,000 credits (7,614,290)
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
Send message
Joined: 19 Aug 12
Posts: 673
ID: 164101
Credit: 305,042,960
RAC: 0
GFN Double Silver: Earned 200,000,000 credits (305,042,960)
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.

Profile JeppeSNProject donor
Avatar
Send message
Joined: 5 Apr 14
Posts: 1549
ID: 306875
Credit: 35,940,187
RAC: 10,456
Found 1 prime in the 2020 Tour de Primes321 LLR Gold: Earned 500,000 credits (529,293)Cullen LLR Gold: Earned 500,000 credits (611,298)ESP LLR Silver: Earned 100,000 credits (174,818)Generalized Cullen/Woodall LLR Bronze: Earned 10,000 credits (85,939)PPS LLR Jade: Earned 10,000,000 credits (13,422,871)PSP LLR Silver: Earned 100,000 credits (428,457)SoB LLR Silver: Earned 100,000 credits (466,812)SR5 LLR Silver: Earned 100,000 credits (145,419)SGS LLR Silver: Earned 100,000 credits (112,277)TRP LLR Silver: Earned 100,000 credits (342,501)Woodall LLR Silver: Earned 100,000 credits (109,455)321 Sieve (suspended) Silver: Earned 100,000 credits (175,037)PPS Sieve Bronze: Earned 10,000 credits (10,113)AP 26/27 Bronze: Earned 10,000 credits (12,129)GFN Ruby: Earned 2,000,000 credits (2,059,478)WW Turquoise: Earned 5,000,000 credits (9,640,000)PSA Turquoise: Earned 5,000,000 credits (7,614,290)
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
Project administrator
Volunteer tester
Project scientist
Send message
Joined: 21 Mar 19
Posts: 184
ID: 1108183
Credit: 10,383,061
RAC: 6,274
321 LLR Gold: Earned 500,000 credits (640,213)Cullen LLR Bronze: Earned 10,000 credits (82,217)ESP LLR Bronze: Earned 10,000 credits (16,570)Generalized Cullen/Woodall LLR Bronze: Earned 10,000 credits (39,285)PPS LLR Ruby: Earned 2,000,000 credits (3,199,281)PSP LLR Silver: Earned 100,000 credits (106,263)SoB LLR Silver: Earned 100,000 credits (258,849)SR5 LLR Bronze: Earned 10,000 credits (59,499)SGS LLR Silver: Earned 100,000 credits (148,878)TRP LLR Silver: Earned 100,000 credits (195,905)Woodall LLR Bronze: Earned 10,000 credits (40,424)321 Sieve (suspended) Turquoise: Earned 5,000,000 credits (5,001,667)AP 26/27 Bronze: Earned 10,000 credits (72,774)GFN Gold: Earned 500,000 credits (502,872)WW Bronze: Earned 10,000 credits (12,000)
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.

Profile BurProject donor
Volunteer tester
Avatar
Send message
Joined: 25 Feb 20
Posts: 474
ID: 1241833
Credit: 313,509,766
RAC: 996,712
321 LLR Ruby: Earned 2,000,000 credits (2,092,823)Cullen LLR Ruby: Earned 2,000,000 credits (2,315,295)ESP LLR Amethyst: Earned 1,000,000 credits (1,445,099)Generalized Cullen/Woodall LLR Ruby: Earned 2,000,000 credits (2,330,027)PPS LLR Ruby: Earned 2,000,000 credits (2,025,505)PSP LLR Ruby: Earned 2,000,000 credits (2,064,832)SoB LLR Amethyst: Earned 1,000,000 credits (1,669,219)SR5 LLR Ruby: Earned 2,000,000 credits (2,065,004)SGS LLR Ruby: Earned 2,000,000 credits (2,027,649)TRP LLR Ruby: Earned 2,000,000 credits (2,089,856)Woodall LLR Ruby: Earned 2,000,000 credits (2,112,258)321 Sieve (suspended) Ruby: Earned 2,000,000 credits (2,107,153)PPS Sieve Turquoise: Earned 5,000,000 credits (5,096,952)AP 26/27 Turquoise: Earned 5,000,000 credits (5,150,782)GFN Turquoise: Earned 5,000,000 credits (7,510,843)WW Double Silver: Earned 200,000,000 credits (270,420,000)PSA Amethyst: Earned 1,000,000 credits (1,022,470)
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 = 5,000,000

Ravi Fernando
Project administrator
Volunteer tester
Project scientist
Send message
Joined: 21 Mar 19
Posts: 184
ID: 1108183
Credit: 10,383,061
RAC: 6,274
321 LLR Gold: Earned 500,000 credits (640,213)Cullen LLR Bronze: Earned 10,000 credits (82,217)ESP LLR Bronze: Earned 10,000 credits (16,570)Generalized Cullen/Woodall LLR Bronze: Earned 10,000 credits (39,285)PPS LLR Ruby: Earned 2,000,000 credits (3,199,281)PSP LLR Silver: Earned 100,000 credits (106,263)SoB LLR Silver: Earned 100,000 credits (258,849)SR5 LLR Bronze: Earned 10,000 credits (59,499)SGS LLR Silver: Earned 100,000 credits (148,878)TRP LLR Silver: Earned 100,000 credits (195,905)Woodall LLR Bronze: Earned 10,000 credits (40,424)321 Sieve (suspended) Turquoise: Earned 5,000,000 credits (5,001,667)AP 26/27 Bronze: Earned 10,000 credits (72,774)GFN Gold: Earned 500,000 credits (502,872)WW Bronze: Earned 10,000 credits (12,000)
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.

Profile JeppeSNProject donor
Avatar
Send message
Joined: 5 Apr 14
Posts: 1549
ID: 306875
Credit: 35,940,187
RAC: 10,456
Found 1 prime in the 2020 Tour de Primes321 LLR Gold: Earned 500,000 credits (529,293)Cullen LLR Gold: Earned 500,000 credits (611,298)ESP LLR Silver: Earned 100,000 credits (174,818)Generalized Cullen/Woodall LLR Bronze: Earned 10,000 credits (85,939)PPS LLR Jade: Earned 10,000,000 credits (13,422,871)PSP LLR Silver: Earned 100,000 credits (428,457)SoB LLR Silver: Earned 100,000 credits (466,812)SR5 LLR Silver: Earned 100,000 credits (145,419)SGS LLR Silver: Earned 100,000 credits (112,277)TRP LLR Silver: Earned 100,000 credits (342,501)Woodall LLR Silver: Earned 100,000 credits (109,455)321 Sieve (suspended) Silver: Earned 100,000 credits (175,037)PPS Sieve Bronze: Earned 10,000 credits (10,113)AP 26/27 Bronze: Earned 10,000 credits (12,129)GFN Ruby: Earned 2,000,000 credits (2,059,478)WW Turquoise: Earned 5,000,000 credits (9,640,000)PSA Turquoise: Earned 5,000,000 credits (7,614,290)
Message 147907 - Posted: 26 Jan 2021 | 19:01:59 UTC - in response to Message 147902.
Last modified: 26 Jan 2021 | 19:06:51 UTC

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
Send message
Joined: 19 Aug 12
Posts: 673
ID: 164101
Credit: 305,042,960
RAC: 0
GFN Double Silver: Earned 200,000,000 credits (305,042,960)
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.

Post to thread

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

[Return to PrimeGrid main page]
DNS Powered by DNSEXIT.COM
Copyright © 2005 - 2021 Rytis Slatkevičius (contact) and PrimeGrid community. Server load 0.97, 0.50, 0.46
Generated 25 Oct 2021 | 23:30:36 UTC