mersenneforum.org > Math Elliptic Curves for Proving that a Wagstaff number is prime?
 Register FAQ Search Today's Posts Mark Forums Read

2023-06-08, 12:53   #12
Dr Sardonicus

Feb 2017
Nowhere

3×7×311 Posts

Quote:
 Originally Posted by T.Rex "Elliptic Curves for Proving that a Wagstaff number is prime" : I should have added a question mark at the end, yes.
Done!

 2023-06-09, 20:54 #13 T.Rex     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): $x_1=4 \ , \ x_{j+1} = \frac{x_j^4+2x_j^2+1}{4(x_j^3-x_j)}$ $\text{If } \ x_{2^{n-1}} \equiv 0 \ \pmod{F_n} \ , \ \text{then } F_n = 2^{2^n}+1 \text{ is prime} .$ And this following test looks exactly my test with DST method for Wagstaff numbers (seed=3, more steps, and final test with -1/3): $x_1=3 \ , \ x_{j+1} = \frac{x_j^4+2x_j^2+1}{4(x_j^3-x_j)}$ $\text{If } \ x_{2^{n}-1} \equiv -1/3 \ \pmod{F_n} \ , \ \text{then } F_n = 2^{2^n}+1 \text{ is prime} .$ 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=q-1;xF=Mod(-1/3,w); x=x1; for(i=2,iF, x=Mod((x^4+2*x^2+1)/(4*x*(x^2-1)),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(" ")); For n=4, for which -1/3=43691, it gives with seed=3 : Code: 19116 5433 17830 3117 4769 23216 21846 46421 60104 47707 62420 60768 42321 43691 2^2^4 is prime ! That's weird ! Moreover, looking at the DiGraph under (x^4+2*x^2+1)/(4*x*(x^2-1)) 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^2-2 modulo a Wagstaff). Last fiddled with by T.Rex on 2023-06-09 at 21:13
2023-06-09, 21:51   #14
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

1DD216 Posts

Quote:
 Originally Posted by T.Rex 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): $x_1=4 \ , \ x_{j+1} = \frac{x_j^4+2x_j^2+1}{4(x_j^3-x_j)}$ $\text{If } \ x_{2^{n-1}} \equiv 0 \ \pmod{F_n} \ , \ \text{then } F_n = 2^{2^n}+1 \text{ is prime} .$ And this following test looks exactly my test with DST method for Wagstaff numbers (seed=3, more steps, and final test with -1/3): $x_1=3 \ , \ x_{j+1} = \frac{x_j^4+2x_j^2+1}{4(x_j^3-x_j)}$ $\text{If } \ x_{2^{n}-1} \equiv -1/3 \ \pmod{F_n} \ , \ \text{then } F_n = 2^{2^n}+1 \text{ is prime} .$ Moreover, looking at the DiGraph under (x^4+2*x^2+1)/(4*x*(x^2-1)) 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^2-2 modulo a Wagstaff).
May I suggest that you consult with Noam Elkies?

2023-06-10, 01:01   #15
Andrew Usher

Dec 2022

2·3·7·13 Posts

Quote:
 Originally Posted by T.Rex I'm an amateur, not a true mathematician. Anyway, I have time to explore stuff and I hope to find something interesting from time to time or to give ideas to true mathematicians. It's the goal of this thread: say to people expert in Elliptic Curves for Primality Proving that there is something interesting which may lead to something worth.
I am not such, clearly. I do not know if anyone here can help you; certainly I'd imagine that those posters that have cluttered this thread with off-topic criticism of me are not able to. And further you say that you've talked to real mathematicians knowledgeable about ECs that also can't. So maybe it does need to be considered a dead end, at least without much deeper knowledge than you or I could possess (written before seeing the last comment from Bob Silverman).

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 faster-than-ECPP proofs for non-smooth 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.

2023-06-10, 10:53   #16
T.Rex

Feb 2004
France

16658 Posts

Quote:
 Originally Posted by R.D. Silverman May I suggest that you consult with Noam Elkies?
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 2023-06-10 at 11:14

2023-06-10, 11:14   #17
T.Rex

Feb 2004
France

13·73 Posts

Quote:
 Originally Posted by Andrew Usher I am not such, clearly. I do not know if anyone here can help you; certainly I'd imagine that those posters that have cluttered this thread with off-topic criticism of me are not able to. And further you say that you've talked to real mathematicians knowledgeable about ECs that also can't. So maybe it does need to be considered a dead end, at least without much deeper knowledge than you or I could possess (written before seeing the last comment from Bob Silverman). 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 faster-than-ECPP proofs for non-smooth 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.
Building a Primality Proof with the EC technic seems a huge work, probably 8 to 12 pages of complex stuff, after a lot of research work I guess.
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...

 2023-06-14, 13:28 #18 T.Rex     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 $(x^4 + 2x^2+ 1) / (4(x^3-x))$ 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=q-2 , and the number N of cycles of length q-2 is 2 times a(q-2) !! See also paper "On different families of invariant irreducible polynomials over F2" by Jean Francis Michon, Philippe Ravache, 2009-2010 , 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 $x^2-2$ modulo a Wagstaff prime. See: DiGraph under x^2-2 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(q-2) -------------------- 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 ...
 2023-06-14, 19:19 #19 T.Rex     Feb 2004 France 13·73 Posts Now with q=31 : Code:  q L N a(q-2) ------------------------ 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 It looks like there are only q-2 cycles when q-2 is prime, or when q=6k+1 .

 Similar Threads Thread Thread Starter Forum Replies Last Post RedGolpe Math 6 2021-01-29 22:29 bhelmes Math 3 2018-09-10 07:31 WraithX Math 12 2010-09-29 09:34 wpolly GMP-ECM 5 2007-07-18 13:18 otkachalka Factoring 5 2005-11-20 12:22

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

Sun Oct 1 15:44:54 UTC 2023 up 18 days, 13:27, 0 users, load averages: 0.77, 0.82, 0.78