## Other

drummers-lowrise

Message boards : General discussion : GF divisibility testing

 Subscribe SortOldest firstNewest firstHighest rated posts first
Author Message
Roger
Volunteer developer
Volunteer tester

Joined: 27 Nov 11
Posts: 1137
ID: 120786
Credit: 267,535,355
RAC: 0

Message 84055 - Posted: 16 Mar 2015 | 20:01:58 UTC

9*2^3497442+1
This Mega prime was found back in 2012:

>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?

serge

Joined: 21 Jun 12
Posts: 112
ID: 144858
Credit: 237,968,345
RAC: 0

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).

Roger
Volunteer developer
Volunteer tester

Joined: 27 Nov 11
Posts: 1137
ID: 120786
Credit: 267,535,355
RAC: 0

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

JeppeSN

Joined: 5 Apr 14
Posts: 1378
ID: 306875
Credit: 21,623,822
RAC: 0

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

Roger
Volunteer developer
Volunteer tester

Joined: 27 Nov 11
Posts: 1137
ID: 120786
Credit: 267,535,355
RAC: 0

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.

JeppeSN

Joined: 5 Apr 14
Posts: 1378
ID: 306875
Credit: 21,623,822
RAC: 0

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