New Generalized Fermat factors

[Batalov]

Looks new. You want to report it to W.Keller:
http://www.prothsearch.net/GFNfacs.html
You were in the right zone, just above the previous search limit:
http://www.prothsearch.net/GFNsrch.txt

[firejuggler]

I did, it is a copy of the mail I just sent. the last time I checked it, the search limit was different.... oh well, that will remove some test for the following exponent. Onward to F6152.

[Batalov]

A previously missed GF(10) factor was updated by PGrid, a year+ after.

[c10ck3r]

Originally Posted by Batalov

A previously missed GF(10) factor was updated by PGrid, a year+ after.

Is there a quick way to test all megabit primes they've found of this form for gf divisibility?

[Batalov]

Of course. pfgw -gxo -q"insert number here"
(in case of the number above, pfgw -gxo -q"9*2^3497442+1",
but for validation that it is a GF(10), pfgw -gos10 -q"9*2^3497442+1" would work. Add -a1 for a different FFT size, to double-check.)

[Batalov]

Here are some thoughts (and a placeholder for a picture) for the specific Proth prime numbers (k=3). There are not original, just mental floss.
This is related to the latest large Proth prime 3*2^10829346+1

To start with, it divides GF(10829343,3), GF(10829345,5), GF(10829344,8) (the algebraic cofactor of it), and GF(10829345,11).

Originally Posted by Yves Gallot

A prime of the form 3*2^n+1, where n is even, cannot be a factor of any Fermat number.
See http://www.ams.org/journals/proc/195...958-0096614-7/

Yves

Once again, thanks, Yves, what a nice article for mental floss! It is interesting that they only added the last (E.Lehmer's) note in proof. Thinking a little longer...

Let p=3*2^n+1, calculations be mod p, and consider a sequence s(0)=b>1, s(k)=s(k-1)^2, 1<=k<=n.
The final residues of the n squarings (in any base b) are cube roots of 1 (mod p), because after cubing we get the Fermat’s little theorem b^(p-1)=1 (mod p). If the final residue is 1, then the paths leading to it are only through square roots of 1, which are 1 and -1, so after a few steps back we have a GF divisor (because the initial value was b>1, not all residues are equal to 1, so there exists an iteration with value -1). The other two roots are L and M, such that L+M=-1, L·M=1, L^2=M, and M^2=L (mod p). For p=3*2^n+1 and n even, they happen to be L=±3(2^(n-1)-2^(n/2-1)), M=±3(2^(n-1)+2^(n/2-1)) and are related to Aurifeuillean factors of 2^(2n-2). (+- signs are as in Robinson’s).

They are coincidentally the solutions to the length-2 cycle question: which values x lead to length-2 cycles in the sequence s(n)? This requires x^4=x, which (with x≠0) is equivalent to x^3=1, and therefore (x-1)*(x^2+x+1)=0 (mod p). x=1, or x=L, or x=M. These roots x form some of the possible entrances into terminal cycles of squaring (in addition to trivial -1 -> 1 -> 1...): -L -> M -> L -> M -> L... and -M -> L ->M -> L ->M...

Indeed, all these paths in different combinations are observed for b=2, 3, 5, 7, 11. For a composite base c GF-divisor test, the residues s(m,b_i) (where b_i are the prime factorization of c) have to be multiplied and the product to be -1 for p|GF(m,c). For example, b=5 and b=11 have final values (for n-2<=m<= n), {R, -1, 1} and {-R,-1,1} respectively, where R is the smaller (“positive”) sqrt(-1) (mod(p)). So, p divides xGF(n-2,5,11) and some GF(•,55). For c=14=2·7, p divides GF(n-2,14), because -L·M=-1. OTOH, products of L and M values are again values L, M or 1. Square roots of L are ±M, and likewise for M. Combinatorial products of -1, –L or –M with some L, M or 1s, produce the desired -1, for example, p divides GF(n-1,70), because s(n-1,70)=-1·L·M=-1. p also divides GF(n-2,8), because -L³=-1.

Some xGFs can be calculated for (1<a<b<=12), e.g. p divides xGF(n-4,7,4), xGF(n-3,7,12), xGF(n-2,3,8), xGF(n-2,9,8), xGF(n-2,5,11), xGF(n-1,3,5), xGF(n-1,8,5), xGF(n-1,9,5), xGF(n-1,3,11), xGF(n-1,8,11), xGF(n-1,9,11), etc. See attached table.

[PBMcL]

I believe that some time back in the 1980's or early 90's Hiromi Suyama noticed that Morehead's Theorem (as quoted by Gallot above) extends to any prime of the form 3*(k^2)*2^n + 1 with n even and k odd, with essentially the same proof. He published this in the AMS Abstracts, but unfortunately there are no online archives available that I could find.

[Batalov]

It is interesting that out of 48 known Proth primes with k=3 and n>1, 40 divide GF(•,3) (including the last one).
The 48 primes are in two classes n mod 3:

• 3|n (majority, 35 of them, and all divide GF(•,3) *) and
• n=3k+2 (minority, 13 of them; 5 divide and 8 don't: with n= 2, 5, 8, 353, 2816, 20909, 42665, 362765). This is roughly 1/k as expected.

This is similar to divisibility of F(•), but the "luck" is in reverse.
The 48 primes are in two classes n mod 2:

• even (majority, 28 of them, and none divide F(•)) and
• odd (minority, 20 of them; of which 8 divide F(•)). This is roughly 1/k as expected.

________________

*There is probably a rather simple proof, too? A la Morehead/Suyama?

[PBMcL]

Originally Posted by PBMcL

I believe that some time back in the 1980's or early 90's Hiromi Suyama noticed that Morehead's Theorem (as quoted by Gallot above) extends to any prime of the form 3*(k^2)*2^n + 1 with n even and k odd, with essentially the same proof. He published this in the AMS Abstracts, but unfortunately there are no online archives available that I could find.

Sorry for the above post - either my memory has failed (a strong possibility) and I forgot some detail of what Suyama actually claimed, or Suyama missed something, since Keller shows 243*2^495732+1 divides F495728, and 243=3*(9^2).

[PBMcL]

Originally Posted by PBMcL

Sorry for the above post - either my memory has failed (a strong possibility) and I forgot some detail of what Suyama actually claimed, or Suyama missed something, since Keller shows 243*2^495732+1 divides F495728, and 243=3*(9^2).

I see my error; the condition wasn't k odd but k=+/-1 mod 6. Then the unique representation of a prime N = 3*(k^2)*2^n+1 (n even) in the form A^2 + 3*B^2 will have A=1 and B=k*2^(n/2). When k is not divisible by 3, 2 is not a cubic residue and N cannot be a Fermat factor.

[Batalov]

Yves shared a reference to the Calvo (2000) paper. Indeed, his theorem 2.1 explains the special case k|n and more.