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 : General discussion : GF divisibility testing

Author Message
Profile Roger
Volunteer developer
Volunteer tester
Avatar
Send message
Joined: 27 Nov 11
Posts: 1137
ID: 120786
Credit: 267,535,355
RAC: 0
Found 1 prime in the 2018 Tour de Primes321 LLR Ruby: Earned 2,000,000 credits (2,037,982)Cullen LLR Ruby: Earned 2,000,000 credits (2,015,907)ESP LLR Ruby: Earned 2,000,000 credits (2,232,391)Generalized Cullen/Woodall LLR Ruby: Earned 2,000,000 credits (2,088,705)PPS LLR Ruby: Earned 2,000,000 credits (2,962,062)PSP LLR Ruby: Earned 2,000,000 credits (2,539,644)SoB LLR Ruby: Earned 2,000,000 credits (2,122,524)SR5 LLR Ruby: Earned 2,000,000 credits (2,238,295)SGS LLR Ruby: Earned 2,000,000 credits (4,149,199)TRP LLR Ruby: Earned 2,000,000 credits (2,125,391)Woodall LLR Ruby: Earned 2,000,000 credits (2,037,732)321 Sieve Turquoise: Earned 5,000,000 credits (5,190,731)Cullen/Woodall Sieve (suspended) Silver: Earned 100,000 credits (207,387)Generalized Cullen/Woodall Sieve (suspended) Turquoise: Earned 5,000,000 credits (5,049,697)PPS Sieve Double Bronze: Earned 100,000,000 credits (100,422,123)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Ruby: Earned 2,000,000 credits (3,227,972)TRP Sieve (suspended) Turquoise: Earned 5,000,000 credits (5,021,659)AP 26/27 Sapphire: Earned 20,000,000 credits (20,651,644)GFN Emerald: Earned 50,000,000 credits (57,918,585)PSA Sapphire: Earned 20,000,000 credits (43,298,465)
Message 84055 - Posted: 16 Mar 2015 | 20:01:58 UTC

9*2^3497442+1
This Mega prime was found back in 2012:
http://www.primegrid.com/forum_thread.php?id=4624

In order to learn more about GF divisibility testing I ran a test using the latest version of pfgw:
>pfgw64.exe -gxo -q"9*2^3497442+1"
PFGW Version 3.7.8.64BIT.20141125.Win_Dev [GWNUM 28.5]

It reported an extra Factor that doesn't seem to have been previously reported:
9*2^3497442+1 is a Factor of xGF(3497440,10,7)!!!!
http://primes.utm.edu/primes/page.php?id=109930

Is this significant?
If so how do you verify it?

Profile sergeProject donor
Avatar
Send message
Joined: 21 Jun 12
Posts: 112
ID: 144858
Credit: 237,968,345
RAC: 0
Eliminated 2 conjecture "k"s321 LLR Turquoise: Earned 5,000,000 credits (5,342,838)Cullen LLR Silver: Earned 100,000 credits (158,983)ESP LLR Gold: Earned 500,000 credits (505,527)Generalized Cullen/Woodall LLR Ruby: Earned 2,000,000 credits (2,268,642)PPS LLR Sapphire: Earned 20,000,000 credits (39,140,538)PSP LLR Silver: Earned 100,000 credits (120,541)SoB LLR Amethyst: Earned 1,000,000 credits (1,280,028)SR5 LLR Ruby: Earned 2,000,000 credits (2,649,390)SGS LLR Gold: Earned 500,000 credits (518,356)TRP LLR Silver: Earned 100,000 credits (141,131)Woodall LLR Silver: Earned 100,000 credits (116,405)Cullen/Woodall Sieve (suspended) Silver: Earned 100,000 credits (235,088)PPS Sieve Amethyst: Earned 1,000,000 credits (1,031,526)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Gold: Earned 500,000 credits (500,445)TRP Sieve (suspended) Gold: Earned 500,000 credits (507,938)AP 26/27 Amethyst: Earned 1,000,000 credits (1,386,749)GFN Double Bronze: Earned 100,000,000 credits (180,408,687)PSA Silver: Earned 100,000 credits (291,533)
Message 84085 - Posted: 17 Mar 2015 | 18:09:18 UTC - in response to Message 84055.

For smaller numbers, verification with independent code is easy; one could use Pari/GP, and use modular arithmetic explicitly.
Let's take this small factor for example:

5 3 117740 32039 117743 2012

This line from GFNfacs.html means 32039*2^117743+1 is a Factor of xGF(117740,5,3), so let's check that:
Mod(5,32039*2^117743+1)^(2^117740)+Mod(3,32039*2^117743+1)^(2^117740)==0

After a while Pari will report "1" (i.e. "true").

A faster way would be
Mod(5/3,32039*2^117743+1)^(2^117740)+1==0

(Note that modular 5/3 will be turned into a single modular residue first and exponentiated next -- which is twice as fast.)

Pari uses GMPlib, but it is possible to code a short program to the same effect in plain C with GMP.

For larger factors, you have to use GWNUM or maybe (for independence) you can code something on a GPU using cuFFT (or similar). For the former, you can run the same command line but add -a1 or -a2 (or even higher): different FFT sizes will be used and it is less likely that a hardware error will happen in the same way (if there was an error).

Profile Roger
Volunteer developer
Volunteer tester
Avatar
Send message
Joined: 27 Nov 11
Posts: 1137
ID: 120786
Credit: 267,535,355
RAC: 0
Found 1 prime in the 2018 Tour de Primes321 LLR Ruby: Earned 2,000,000 credits (2,037,982)Cullen LLR Ruby: Earned 2,000,000 credits (2,015,907)ESP LLR Ruby: Earned 2,000,000 credits (2,232,391)Generalized Cullen/Woodall LLR Ruby: Earned 2,000,000 credits (2,088,705)PPS LLR Ruby: Earned 2,000,000 credits (2,962,062)PSP LLR Ruby: Earned 2,000,000 credits (2,539,644)SoB LLR Ruby: Earned 2,000,000 credits (2,122,524)SR5 LLR Ruby: Earned 2,000,000 credits (2,238,295)SGS LLR Ruby: Earned 2,000,000 credits (4,149,199)TRP LLR Ruby: Earned 2,000,000 credits (2,125,391)Woodall LLR Ruby: Earned 2,000,000 credits (2,037,732)321 Sieve Turquoise: Earned 5,000,000 credits (5,190,731)Cullen/Woodall Sieve (suspended) Silver: Earned 100,000 credits (207,387)Generalized Cullen/Woodall Sieve (suspended) Turquoise: Earned 5,000,000 credits (5,049,697)PPS Sieve Double Bronze: Earned 100,000,000 credits (100,422,123)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Ruby: Earned 2,000,000 credits (3,227,972)TRP Sieve (suspended) Turquoise: Earned 5,000,000 credits (5,021,659)AP 26/27 Sapphire: Earned 20,000,000 credits (20,651,644)GFN Emerald: Earned 50,000,000 credits (57,918,585)PSA Sapphire: Earned 20,000,000 credits (43,298,465)
Message 84384 - Posted: 25 Mar 2015 | 21:39:26 UTC - in response to Message 84085.

Testing a big factor overflows the PARI stack, so you first have to allocate more memory:

? allocatemem(1000000000) *** Warning: new stack size = 1000000000 (953.674 Mbytes). ? Mod(10/7,9*2^3497442+1)^(2^3497440)+1==0 %8 = 1 ?

Total time 8 days. Factor confirmed. I think time goes up with the square of n, i.e. O(n^2).
I have no NVIDIA card so cuFFT is off the table for me.
I'll have to test PFGW Version 3.7.8 on a few more primes and see if any new factors turn up.
I've reported the factor to W.Keller:
http://www.prothsearch.com/GFNfacs.html

Profile JeppeSNProject donor
Avatar
Send message
Joined: 5 Apr 14
Posts: 1378
ID: 306875
Credit: 21,623,822
RAC: 0
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 (139,922)Generalized Cullen/Woodall LLR Bronze: Earned 10,000 credits (35,236)PPS LLR Turquoise: Earned 5,000,000 credits (9,594,179)PSP LLR Silver: Earned 100,000 credits (212,242)SoB LLR Silver: Earned 100,000 credits (237,390)SR5 LLR Silver: Earned 100,000 credits (145,419)SGS LLR Silver: Earned 100,000 credits (105,212)TRP LLR Silver: Earned 100,000 credits (342,501)Woodall LLR Silver: Earned 100,000 credits (109,455)321 Sieve 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 Amethyst: Earned 1,000,000 credits (1,674,106)PSA Turquoise: Earned 5,000,000 credits (7,614,290)
Message 84385 - Posted: 25 Mar 2015 | 23:04:45 UTC - in response to Message 84384.

Maybe off-topic here, but it seems that Keller has not updated his page on ordinary Fermat factors with the find PrimeGrid did last month. /JeppeSN

Profile Roger
Volunteer developer
Volunteer tester
Avatar
Send message
Joined: 27 Nov 11
Posts: 1137
ID: 120786
Credit: 267,535,355
RAC: 0
Found 1 prime in the 2018 Tour de Primes321 LLR Ruby: Earned 2,000,000 credits (2,037,982)Cullen LLR Ruby: Earned 2,000,000 credits (2,015,907)ESP LLR Ruby: Earned 2,000,000 credits (2,232,391)Generalized Cullen/Woodall LLR Ruby: Earned 2,000,000 credits (2,088,705)PPS LLR Ruby: Earned 2,000,000 credits (2,962,062)PSP LLR Ruby: Earned 2,000,000 credits (2,539,644)SoB LLR Ruby: Earned 2,000,000 credits (2,122,524)SR5 LLR Ruby: Earned 2,000,000 credits (2,238,295)SGS LLR Ruby: Earned 2,000,000 credits (4,149,199)TRP LLR Ruby: Earned 2,000,000 credits (2,125,391)Woodall LLR Ruby: Earned 2,000,000 credits (2,037,732)321 Sieve Turquoise: Earned 5,000,000 credits (5,190,731)Cullen/Woodall Sieve (suspended) Silver: Earned 100,000 credits (207,387)Generalized Cullen/Woodall Sieve (suspended) Turquoise: Earned 5,000,000 credits (5,049,697)PPS Sieve Double Bronze: Earned 100,000,000 credits (100,422,123)Sierpinski (ESP/PSP/SoB) Sieve (suspended) Ruby: Earned 2,000,000 credits (3,227,972)TRP Sieve (suspended) Turquoise: Earned 5,000,000 credits (5,021,659)AP 26/27 Sapphire: Earned 20,000,000 credits (20,651,644)GFN Emerald: Earned 50,000,000 credits (57,918,585)PSA Sapphire: Earned 20,000,000 credits (43,298,465)
Message 85667 - Posted: 17 May 2015 | 20:39:34 UTC

Keller did an update of his pages in April. Both the GF factor I reported and the recent Fermat divisor found in February now appear.

Profile JeppeSNProject donor
Avatar
Send message
Joined: 5 Apr 14
Posts: 1378
ID: 306875
Credit: 21,623,822
RAC: 0
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 (139,922)Generalized Cullen/Woodall LLR Bronze: Earned 10,000 credits (35,236)PPS LLR Turquoise: Earned 5,000,000 credits (9,594,179)PSP LLR Silver: Earned 100,000 credits (212,242)SoB LLR Silver: Earned 100,000 credits (237,390)SR5 LLR Silver: Earned 100,000 credits (145,419)SGS LLR Silver: Earned 100,000 credits (105,212)TRP LLR Silver: Earned 100,000 credits (342,501)Woodall LLR Silver: Earned 100,000 credits (109,455)321 Sieve 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 Amethyst: Earned 1,000,000 credits (1,674,106)PSA Turquoise: Earned 5,000,000 credits (7,614,290)
Message 91797 - Posted: 1 Feb 2016 | 23:53:23 UTC - in response to Message 85667.

Keller did an update of his pages in April. Both the GF factor I reported and the recent Fermat divisor found in February now appear.


Cool.

Now, since then http://www.fermatsearch.org/news.html has reported five new factors of "classical" Fermat numbers F(m), so Keller's http://www.prothsearch.com/fermat.html needs to be updated again.

/JeppeSN

Message boards : General discussion : GF divisibility testing

[Return to PrimeGrid main page]
DNS Powered by DNSEXIT.COM
Copyright © 2005 - 2022 Rytis Slatkevičius (contact) and PrimeGrid community. Server load 0.05, 0.04, 0.00
Generated 6 Jul 2022 | 10:39:39 UTC