20230608, 12:53  #12 
Feb 2017
Nowhere
3×7×311 Posts 

20230609, 20:54  #13 
Feb 2004
France
13·73 Posts 
About the DST test for Fermat numbers, I've done some research (with graphviz and Pari/gp) and I've found that there are other seeds that work fine for "proving" (experimently only) that a Fermat number is prime.
The following test looks exactly the LLT for Mersenne numbers (seed=4, and final test with 0): And this following test looks exactly my test with DST method for Wagstaff numbers (seed=3, more steps, and final test with 1/3): Pari/gp code for the 3 tests (change the line which defines x1, iF and xF): Code:
ECPTF(n,p)= { q=2^n; w=2^q+1; x1=5;iF=q/2;xF=Mod(1,w); x1=4;iF=q/2;xF=Mod(0,w); x1=3;iF=q1;xF=Mod(1/3,w); x=x1; for(i=2,iF, x=Mod((x^4+2*x^2+1)/(4*x*(x^21)),w); if(p==1,print(lift(x))); ); if(p==0,print(lift(x))); if(x == xF, printf("2^2^%d is prime !\n\n", n); , printf("2^2^%d is composite !\n\n", n); ) } ECPTF(3,1); ECPTF(4,1); for(n=2,10,ECPTF(n,0);print(" ")); Code:
19116 5433 17830 3117 4769 23216 21846 46421 60104 47707 62420 60768 42321 43691 2^2^4 is prime ! Moreover, looking at the DiGraph under (x^4+2*x^2+1)/(4*x*(x^21)) for Fermat and Wagstaff numbers, they are different.  Fermat: there are 3 big trees ending at: 1, 1, and 0. Plus a small cycle, plus plenty of cycles.  Wagstaff: there are only cycles ! (like for the DiGraph under x^22 modulo a Wagstaff). Last fiddled with by T.Rex on 20230609 at 21:13 
20230609, 21:51  #14  
"Bob Silverman"
Nov 2003
North of Boston
1DD2_{16} Posts 
Quote:


20230610, 01:01  #15  
Dec 2022
2·3·7·13 Posts 
Quote:
No, ECs are not only for smooth numbers  that's what ECPP is about  but clearly you're looking for something better (faster, thus usable for larger numbers) than that. If you have researched as much as that and still haven't found anything suggesting fasterthanECPP proofs for nonsmooth numbers are possible, it's reasonable to think that perhaps they aren't. Indeed, I also have seen no suggestion of the sort, and I think no primality proof for general numbers that can beat O(n^4) seems possible from any currently known mathematics. 

20230610, 10:53  #16 
Feb 2004
France
1665_{8} Posts 
Why not ! It seems he knows this subject quite well.
However, first, I have to sum all of this in a clean and clear paper. Last fiddled with by T.Rex on 20230610 at 11:14 
20230610, 11:14  #17  
Feb 2004
France
13·73 Posts 
Quote:
I've discussed with EC experts who did not say they cannot build a proof but rather that they will think about this problem. Based on a comment by Alon Amit in Quora about another very complex problem proved by EC, he suggested that there are about only 200 to 400 people in the world who master EC. They are probably very busy with other stuff and are not reading the GIMPS forum. So, I think it is not a dead end (using EC for building a PP for Wagstaff numbers) yet. It will be a dead end when one (or several) EC expert will say that there is no way. And my opinion about what EC can do and cannot do has no value, yet (maybe in 1 year or 2... ๐). I'm just asking... 

20230614, 13:28  #18 
Feb 2004
France
13·73 Posts 
I have computed (by means of some Pari/gp and awk programs) the number of cycles of the digraph under modulo a Wagstaff prime.
And I again find results related to "irreducible polynomials over F2" !! See a(n) in: https://oeis.org/A165921/list Every prime Wq has cycles of length L=q2 , and the number N of cycles of length q2 is 2 times a(q2) !! See also paper "On different families of invariant irreducible polynomials over F2" by Jean Francis Michon, Philippe Ravache, 20092010 , page 173, h6 column. (Not sure I will be able to compute the cycles for W31... too big). (About W29, modulo crashes since sometimes denominator is 0). As a reminder, I found the same kind of relationship when computing the number of cycles of the digraph under modulo a Wagstaff prime. See: DiGraph under x^22 modulo a Wagstaff number . So, there is a solid link between the Wagstaff primes and the "irreducible polynomials over F2". Tony Code:
q L N a(q2)  7 5 2 1  11 1 2 3 2 9 18 9  13 11 62 31  17 1 1 5 6 15 726 363  19 17 2570 1285  23 1 1 7 18 21 33282 16641  31 ... not easy ... 
20230614, 19:19  #19 
Feb 2004
France
13·73 Posts 
Now with q=31 :
Code:
q L N a(q2)  7 5 2 1  11 1 2 3 2 9 18 9  13 11 62 31  17 1 1 5 6 15 726 363  19 17 2570 1285  23 1 1 7 18 21 33282 16641  31 29 6170930 3085465 
Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Number of points on elliptic curves over finite fields  RedGolpe  Math  6  20210129 22:29 
multiplication defined by elliptic curves ?  bhelmes  Math  3  20180910 07:31 
Need help with elliptic curves...  WraithX  Math  12  20100929 09:34 
New coordinate system for elliptic curves  wpolly  GMPECM  5  20070718 13:18 
Elliptic curves in NFS  otkachalka  Factoring  5  20051120 12:22 