Elliptic Curves for Proving that a Wagstaff number is prime? - Page 2

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

Quote:

Originally Posted by T.Rex

<snip>
"Elliptic Curves for Proving that a Wagstaff number is prime" : I should have added a question mark at the end, yes.
<snip>

Done!

T.Rex · 2023-06-09, 20:54

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

R.D. Silverman · 2023-06-09, 21:51

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} .$

<snip> <snip>

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?

Andrew Usher · 2023-06-10, 01:01

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.

T.Rex · 2023-06-10, 10:53

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.

T.Rex · 2023-06-10, 11:14

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

T.Rex · 2023-06-14, 13:28

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

T.Rex · 2023-06-14, 19:19

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 .

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+2x^2+1)/(4x(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+2x^2+1)/(4x(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-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 ...

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Number of points on elliptic curves over finite fields	RedGolpe	Math	6	2021-01-29 22:29
multiplication defined by elliptic curves ?	bhelmes	Math	3	2018-09-10 07:31
Need help with elliptic curves...	WraithX	Math	12	2010-09-29 09:34
New coordinate system for elliptic curves	wpolly	GMP-ECM	5	2007-07-18 13:18
Elliptic curves in NFS	otkachalka	Factoring	5	2005-11-20 12:22