mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2014-01-03, 19:33   #100
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

221658 Posts
Default

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
Batalov is offline   Reply With Quote
Old 2014-01-03, 19:39   #101
firejuggler
 
firejuggler's Avatar
 
Apr 2010
Over the rainbow

2×5×11×23 Posts
Default

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.

Last fiddled with by firejuggler on 2014-01-03 at 19:41
firejuggler is online now   Reply With Quote
Old 2014-01-14, 17:40   #102
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

221658 Posts
Default

A previously missed GF(10) factor was updated by PGrid, a year+ after.
Batalov is offline   Reply With Quote
Old 2014-01-14, 20:42   #103
c10ck3r
 
c10ck3r's Avatar
 
Aug 2010
Kansas

10438 Posts
Default

Quote:
Originally Posted by Batalov View Post
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?
c10ck3r is offline   Reply With Quote
Old 2014-01-14, 21:13   #104
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

32×17×61 Posts
Default

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 is offline   Reply With Quote
Old 2014-01-21, 00:06   #105
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

100100011101012 Posts
Default

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

Quote:
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 -L3=-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.
Attached Thumbnails
Click image for larger version

Name:	Residues.png
Views:	95
Size:	6.3 KB
ID:	10691  

Last fiddled with by Batalov on 2014-01-21 at 07:52 Reason: fixed typos and errors
Batalov is offline   Reply With Quote
Old 2014-01-21, 06:19   #106
PBMcL
 
PBMcL's Avatar
 
Jan 2005

2·31 Posts
Default

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.
PBMcL is offline   Reply With Quote
Old 2014-01-21, 07:13   #107
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

32·17·61 Posts
Default

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?

Last fiddled with by Batalov on 2014-01-21 at 09:45
Batalov is offline   Reply With Quote
Old 2014-01-21, 15:16   #108
PBMcL
 
PBMcL's Avatar
 
Jan 2005

6210 Posts
Default

Quote:
Originally Posted by PBMcL View Post
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 is offline   Reply With Quote
Old 2014-01-21, 19:36   #109
PBMcL
 
PBMcL's Avatar
 
Jan 2005

2×31 Posts
Default

Quote:
Originally Posted by PBMcL View Post
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.
PBMcL is offline   Reply With Quote
Old 2014-01-21, 19:38   #110
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

32×17×61 Posts
Default

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

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Generalized Fermat numbers (in our case primes) pepi37 Conjectures 'R Us 4 2015-10-09 14:49
Pseudoprimality Hypothesis for Specific Class of Generalized Fermat Numbers primus Miscellaneous Math 1 2015-03-25 22:18
Generalized Fermat factors - why? siegert81 Factoring 1 2011-09-05 23:00
Generalized Fermat Numbers ET_ Programming 4 2008-06-23 07:59
Generalized Fermat Prime Search? pacionet Lounge 3 2006-01-25 15:40

All times are UTC. The time now is 12:15.

Mon Mar 8 12:15:11 UTC 2021 up 95 days, 8:26, 0 users, load averages: 2.16, 1.72, 1.62

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.