Elliptic Curves for Proving that a Wagstaff number is prime?

T.Rex · 2023-06-01, 15:36

I've spent some time looking at papers dealing with Elliptic Curves used for Primality Proving.

All the papers that I've found yet are dealing only with smooth numbers (numbers equal to N-1 or N+1 where N is easily or partly factored).

Two of them deal with Fermat numbers:
Elliptic curve primality tests for Fermat and related primes by Denomme & Savin (2007-2008)
PRIMALITY TESTS FOR FERMAT NUMBERS AND ... by Tsumura (2009)

The test by Tsumura appears at page 7.

$x_0=5 \ , \ x_{j+1} = \frac{x_j^4+2x_j^2+1}{4(x_j^3-x_j)}$

$\text{If } \ x_{2^{k-1}-1} \equiv \pm 1 \ \pmod{F_k} \ , \ \text{then } F_k \text{ is prime} .$

The test in Denomme & Savin appears in Chapter 4 at page 7 as:

$x_1 = 5 \ , \ x_{m+1} = 1/2(\frac{x_m}{i} + \frac{i}{x_m})$

$F_n \text{ is prime iff } x_{2^k} \ \equiv \ 0 \ \pmod{2^{2^k}+i}$

Though this looks weird, and since $x_{2j}$ is a fraction where the imaginary number $i$ does not appear, it is possible to transform the test in exactly Tsumura's test, with a coefficient $S = \pm 1$ .

So that the equivalent Pari/gp code for both Denomme/Savin and Tsumura methods is:

Code:

S=-1;
ECPTF(n,p)=
{
q=2^n;w=2^q+1;x1=5;x=x1;
for(i=2,q/2,
        x=S*(Mod(x^4+2*x^2+1,w)/Mod(4*x*(x^2-1),w));
        if(p==1,print(lift(Mod(numerator(x),w))," ",lift(Mod(denominator(x),w))));
);
if(p==0,print(lift(Mod(numerator(x),w))," ",lift(Mod(denominator(x),w))));
if(Mod(numerator(x),w) == Mod(-S,w),
        printf("2^2^%d is prime !\n\n", n);
        ,
        printf("2^2^%d is composite !\n\n", n);
)
}

ECPTF(4,1);
for(n=2,10,ECPTF(n,0));

(with S=1 or S=-1 for Tsumura or Delomme)

which generates the following result:

Code:

9283 1
25064 1
26225 1
40394 1
3300 1
4079 1
1 1
2^2^4 is prime !

1 1
2^2^2 is prime !

1 1
2^2^3 is prime !

1 1
2^2^4 is prime !

422839282 1
2^2^5 is composite !

Now, changing only:
- the seed: $\ \ \ \ \ \ \ \ \ \ \ \ \ x1 = 5 \ \longrightarrow \ 3$ ,
- the number of steps: $2^{n-1} \ \longrightarrow \ q-2$ ,
- the final test: $\ \ \ \ \ \ \ \equiv \pm 1 \ \longrightarrow \ \equiv \pm 2^{(q+1)/2} - 1$
- and the modulo: $\ \ \ \ F_n=2^{2^n}+1 \ \longrightarrow \ W_q = \frac{2^q+1}{3}$
I've got a PRP test for Wagstaff numbers:

Code:

S=-1;
ECPTF(q,p)=
{
w=(2^q+1)/3;
x1=3;x=x1;
if(p>0,print("W",q,": ",w));
if(p>1,print("2^((q+1)/2): ",2^((q+1)/2)));
for(i=2,q-2,
        x=S*(Mod(x^4+2*x^2+1,w)/Mod(4*x*(x^2-1),w));
        if(p>0,printf("%3d %20d %20d\n",i,lift(Mod(numerator(x),w)),lift(Mod(-numerator(x),w))));
);
\\if(p==0,print(lift(Mod(numerator(x),w))," ",lift(Mod(denominator(x),w))));
if(lift(Mod(numerator(x),w)) ==     2^((q+1)/2) - 1
   ||
   lift(Mod(numerator(x),w)) == w - 2^((q+1)/2) - 1,
        printf("W%d is prime !\n", q)
        ,
        if(p>0,printf("W%d is composite.\n", q))
)
}

ECPTF(11,2);
ECPTF(13,2);
ECPTF(17,2)
print(" ");
forprime(q=19,15000,ECPTF(q,0));

generating:

Code:

W11: 683
2^((q+1)/2): 64
  2                  371                  312
  3                  181                  502
  4                  130                  553
  5                  112                  571
  6                  111                  572
  7                  498                  185
  8                  134                  549
  9                  618                   65
W11 is prime !
W13: 2731
2^((q+1)/2): 128
  2                 2161                  570
  3                 2521                  210
  4                 1210                 1521
  5                 1233                 1498
  6                 2351                  380
  7                  829                 1902
  8                   98                 2633
  9                 2385                  346
 10                 1139                 1592
 11                 2602                  129
W13 is prime ! (2602)
W17: 43691
2^((q+1)/2): 512
  2                20024                23667
  3                39018                 4673
  4                 4921                38770
  5                17563                26128
  6                30707                12984
  7                37996                 5695
  8                25024                18667
  9                20891                22800
 10                 6366                37325
 11                30467                13224
 12                19227                24464
 13                25456                18235
 14                15993                27698
 15                  511                43180
W17 is prime ! (511)

W19 is prime !
W23 is prime !
W31 is prime !
W43 is prime !
W61 is prime !
W79 is prime !
W101 is prime !
W127 is prime !
W167 is prime !
W191 is prime !
W199 is prime !
W313 is prime !
W347 is prime !
W701 is prime !
W1709 is prime !
...

Which leads to a new conjectured PRP Test for Wagstaff numbers (Denomme-Savin-Tsumura-Reix):

$x_0=3 \ , \ x_{j+1} = \frac{x_j^4+2x_j^2+1}{4(x_j^3-x_j)}$

$\text{If } \ x_{q-2} \ \equiv \ \pm \ 2^{(q+1)/2} - 1 \ \pmod{W_q} \ , \ \text{then } W_q = \frac{2^q+1}{3} \text{ is PRobably Prime} .$

(The sign on $2^{(q+1)/2}$ seems to depend on $q \ \pmod{12}$ :
- minus when $\equiv 1 \text{ or } 11$
- plus when $\equiv 5 \text{ or } 7$
)

So, it is possible to keep the core of a "Primality Test using Elliptic Curve theory and designed for Fermat numbers" and build a PRP Test for Wagstaff numbers (which are close to Fermat numbers in some way).
Weird!

Now, the questions:
- How to prove this PRP test?
- Can we build a Primality Test with it?
- Can we reuse Delomme/Savin/Tsumura method for proving this? or do we need something different?

Andrew Usher · 2023-06-03, 01:02

You talk of this as a 'PRP test' here, which again is not a proof (https://mersenneforum.org/showthread.php?t=28305). Since we already have adequate PRP tests, a new one is not of practical importance.

If you speculate this can be converted into a proof, you should be familiar with how this is done with the existing fast deterministic tests and why that approach doesn't work directly for Wagstaffs. Then you might get us somewhere, but the burden of proof is still on you.

T.Rex · 2023-06-03, 05:55

You are right. It's not a PRP test. It is a candidate PRP test.
And we already have plenty of proved PRP tests for Wagstaff numbers, including two by myself, plus the Vrba-Reix test I contributed to a decade ago and which enabled me (as part of a team) to find the biggest Wagstaff PRP at that time.

My goal is to reopen the area: study Elliptic Curves for Wagstaff numbers, which are not smooth, with a new information.

I've started to learn Elliptic Curves (EC), and it is a jungle of complexity, and it will take me months (or years) to be able to understand them and then to master them.
If you master them, please explain us where there are dark and unexplored places in the EC theory that could be used.

I've started to discuss with some today experts of EC used for Primality Proving (PP), and they have started to look at more complex and different kinds of EC for PP for Wagstaff numbers.

My experimental work only shows that a EC method for proving that a Fermat number is prime can be transformed into a possible PRP test for Wagstaff numbers.
Showing that this candidate PRP test can be turned into a true PRP test seems possible, like it was possible to do this with Lucas-Lehmer Sequences theory (as I did several times) thought such theory cannot be used for proving a Primality Test for Wagstaff numbers.

Now, is it impossible to turn this candidate PRP test into a primality proof ? I don't know yet. EC theory seems extremely rich and complex, and I'm not sure that all possibilities have been yet explored. And, if you are able to explain and prove that EC theory cannot be used for proving that a Wagstaff number is prime, please do: the burden of proof is on you.

"They did'nt know it was impossible, so they did it".

T.Rex · 2023-06-03, 14:42

Here is a second version which makes even more sens.

First, consider this unique and simpler version of Denomme-Savin-Tsumura's primality test for Fermat numbers:

$x_1=5 \ , \ 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 \ \pmod{F_n} \ , \ \text{then } F_n = 2^{2^n}+1 \text{ is prime} .$

With Pari/gp code:

Code:

ECPTF(n,p)=
{
q=2^n;
w=2^q+1;
x1=5;x=x1;
for(i=2,q/2,
        x=Mod(x^4+2*x^2+1,w)/Mod(4*x*(x^2-1),w);
        if(p==1,print(lift(Mod(numerator(x),w))));
);
if(p==0,print(lift(Mod(numerator(x),w))));
if(Mod(numerator(x),w) == Mod(-1,w),
        printf("2^2^%d is prime !\n\n", n);
        ,
        printf("2^2^%d is composite !\n\n", n);
)
}

ECPTF(4,1);
for(n=2,10,ECPTF(n,0));

This new version compares the final value of x with -1 .

Now, with my candidate PRP test for Wagstaff numbers:

The variable S (-1 or +1) has been removed.
The number of steps has moved from q-2 to q-1.
And the final test no more depends on q%12.

MOREOVER, it makes MUCH more sens with the following!
Denomme-Savin-Tsumura's primality test for $F_n=2^{2^n}+1$ compares the last value of x with -1.
And now the last step of the new version of my candidate PRP test, since a Wagstaff number is 1/3 of a $2^q+1$ number, compares the last value of x with -1/3 !! Makes sens !!!

Thus the changes from Denomme-Savin-Tsumura's primality test to my candidate PRP test are:
- the seed: $\ \ \ \ \ \ \ \ \ \ \ \ \ x1 = 5 \ \longrightarrow \ 3$ ,
- the number of steps: $2^{n-1} \ \longrightarrow \ q-1$ ,
- the final test: $\ \ \ \ \ \ \ \equiv -1 \ \longrightarrow \ \equiv -1/3$
- and the modulo: $\ \ \ \ F_n=2^{2^n}+1 \ \longrightarrow \ W_q = \frac{2^q+1}{3}$

Code:

ECPTF(q,p)=
{
w=(2^q+1)/3;
x1=3;x=x1;
if(p>0,print("W",q,": ",w));
if(p>1,print("-1/3: ",lift(Mod(-1/3,w))));
for(i=2,q-1,
        x=Mod(x^4+2*x^2+1,w)/Mod(4*x*(x^2-1),w);
        if(p>0,printf("%3d %20d\n",i,lift(Mod(numerator(x),w))));
);
if(lift(Mod(numerator(x),w)) == lift(Mod(-1/3,w)),
               printf("W%d is prime ! \n", q)
        ,
        if(p>0,printf("W%d is composite.\n", q))
)
}

ECPTF(11,2);
ECPTF(13,2);
ECPTF(17,2);
print(" ");
forprime(q=19,15000,ECPTF(q,0));

generating:

Code:

W11: 683
-1/3: 455
  2                  371
  3                  181
  4                  130
  5                  112
  6                  111
  7                  498
  8                  134
  9                  618
 10                  455
W11 is prime !
W13: 2731
-1/3: 910
  2                  570
  3                 2521
  4                 1521
  5                 1233
  6                  380
  7                  829
  8                 2633
  9                 2385
 10                 1592
 11                 2602
 12                  910
W13 is prime !
W17: 43691
-1/3: 29127
  2                23667
  3                39018
  4                38770
  5                17563
  6                12984
  7                37996
  8                18667
  9                20891
 10                37325
 11                30467
 12                24464
 13                25456
 14                27698
 15                  511
 16                29127
W17 is prime !

W19 is prime !
W23 is prime !
W31 is prime !
W43 is prime !
W61 is prime !
W79 is prime !
W101 is prime !
W127 is prime !
W167 is prime !
W191 is prime !
W199 is prime !
W313 is prime !
W347 is prime !
W701 is prime !
W1709 is prime !
W2617 is prime !
W3539 is prime !
W5807 is prime !
...

Which leads to a (probably final) new version of a conjectured PRP Test for Wagstaff numbers (Denomme-Savin-Tsumura-Reix):

$x_1=3 \ , \ x_{j+1} = \frac{x_j^4+2x_j^2+1}{4(x_j^3-x_j)}$

$\text{If } \ x_{q-1} \ \equiv \ -1/3 \ \pmod{W_q} \ , \ \text{then } W_q = \frac{2^q+1}{3} \text{ is PRobably Prime} .<br />$

CQFD.

T.Rex · 2023-06-04, 04:39

The Pari/gp code for the conjectured PRP test for Wagstaff number can be simplified (denominator is always 1):

Code:

ECPTF(q,p)=
{
w=(2^q+1)/3;
x1=3;x=x1;
if(p>0,print("W",q,": ",w));
if(p>1,print("-1/3: ",lift(Mod(-1/3,w))));
for(i=2,q-1,
        x=Mod((x^4+2*x^2+1)/(4*x*(x^2-1)),w);
        if(p>0,printf("%3d %20d \n",i,lift(x)));
);
if(x == Mod(-1/3,w),
               printf("W%d is prime ! \n", q)
     ,
        if(p>0,printf("W%d is composite.\n", q))
)
}

ECPTF(11,2);
ECPTF(13,2);
ECPTF(17,2);
print(" ");
forprime(q=19,15000,ECPTF(q,0));

BTW:
- seed $x_1=5$ in Denome-Savin-Tsumura test for Fermats is: $F_1 = 2^{2^1}+1$ .
- seed $x_1=3$ in candidate PRP test for Wagstaffs is: $\ \ \ \ \ \ \ \ \ W_3 = (2^3+1)/3$ .

Same simplification for the Pari/gp code for Denome-Savin-Tsumura test:

Code:

ECPTF(n,p)=
{
q=2^n;
w=2^q+1;
x1=5;x=x1;
for(i=2,q/2,
        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 == Mod(-1,w),
        printf("2^2^%d is prime !\n\n", n);
        ,
        printf("2^2^%d is composite !\n\n", n);
)
}

ECPTF(4,1);
for(n=2,10,ECPTF(n,0));

Andrew Usher · 2023-06-04, 23:46

Sorry, I didn't realise who you were - you can ignore most of what I said as I'm sure you already know. I haven't investigated the mathematics of elliptic curves and I suppose there's some chance you might find something new - but there's many more skilled mathematicians that have.

However, you did title this thread 'proving prime' when you admittedly have no idea how to even try doing that (obviously, standard ECPP is not what is meant here). No doubt you were inspired by the test for Fermats (again, not of practical importance), but as you state in summary, it seems all proposed fast elliptic-curve tests, like all conventional fast tests, require p+1 or p-1 to be factorable - and presumably for the same reason - and that's precisely the problem. ('Fast' tests are O(n^2) (like PRP) while ECPP is O(n^4), using the best techniques.)

There seems no reason to doubt that the tests you're presenting here are valid PRP test (though slower than normal PRP), but equally no reason to think they might prove primality.

VBCurtis · 2023-06-05, 05:38

Quote:

Originally Posted by Andrew Usher

Sorry, I didn't realise who you were - you can ignore most of what I said as I'm sure you already know.

Yes, we know.

R.D. Silverman · 2023-06-05, 09:39

Quote:

Originally Posted by Andrew Usher

Sorry, I didn't realise who you were - you can ignore most of what I said as I'm sure you already know.

Judging a post because of who wrote it, rather than the content of a post is a classic ad hominem attack.

Quote:

I haven't investigated the mathematics of elliptic curves.

Yet you attacked the post anyway.

Uncwilly · 2023-06-05, 14:28

Quote:

Originally Posted by Andrew Usher

Sorry, I didn't realise who you were

And you seem to continuously forget where you are and the folks that we have hanging around here. Rest assured that for many things being discussed here, you are not the smartest person in the room. You need to learn to deal with that fact.

T.Rex · 2023-06-06, 20:12

Quote:

Originally Posted by Andrew Usher

Sorry, I didn't realise who you were ...

I am one of the numerous and old phantoms of the GIMPS forum. I come, I say some stupid stuff, then I go away for years, then I come back, I say something less stupid, and I go again away for years... ;-)
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.

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

As I said, for now I know nearly nothing about Elliptic Curves. However, based on what I've already read and on some email exchanges with EC experts, there are no-deeply explored yet parts of EC theory (or theories close to EC) that could be used for the Wagstaff numbers (maybe !).

Anyway, if you find a paper saying that EC is only for "smooth" numbers, please let us know. However, ECPP is for any number since it has already been used for several Wagstaff numbers (and I remember I suggested François Morain to use ECPP with one Wagstaff number about 15 (or more?) years ago... I can't remember, so many years!).

mathwiz · 2023-06-08, 02:13

It's probably best to just ignore Andrew Usher, whose posts generally seem to consist of nothing more than nitpicking/jabbing at others, and are entirely devoid of meaningful content.

2023-06-01, 15:36	#1
T.Rex Feb 2004 France 13·73 Posts	Elliptic Curves for Proving that a Wagstaff number is prime? I've spent some time looking at papers dealing with Elliptic Curves used for Primality Proving. All the papers that I've found yet are dealing only with smooth numbers (numbers equal to N-1 or N+1 where N is easily or partly factored). Two of them deal with Fermat numbers: Elliptic curve primality tests for Fermat and related primes by Denomme & Savin (2007-2008) PRIMALITY TESTS FOR FERMAT NUMBERS AND ... by Tsumura (2009) The test by Tsumura appears at page 7. $x_0=5 \ , \ x_{j+1} = \frac{x_j^4+2x_j^2+1}{4(x_j^3-x_j)}$ $\text{If } \ x_{2^{k-1}-1} \equiv \pm 1 \ \pmod{F_k} \ , \ \text{then } F_k \text{ is prime} .$ The test in Denomme & Savin appears in Chapter 4 at page 7 as: $x_1 = 5 \ , \ x_{m+1} = 1/2(\frac{x_m}{i} + \frac{i}{x_m})$ $F_n \text{ is prime iff } x_{2^k} \ \equiv \ 0 \ \pmod{2^{2^k}+i}$ Though this looks weird, and since $x_{2j}$ is a fraction where the imaginary number $i$ does not appear, it is possible to transform the test in exactly Tsumura's test, with a coefficient $S = \pm 1$ . So that the equivalent Pari/gp code for both Denomme/Savin and Tsumura methods is: Code: S=-1; ECPTF(n,p)= { q=2^n;w=2^q+1;x1=5;x=x1; for(i=2,q/2, x=S(Mod(x^4+2x^2+1,w)/Mod(4x(x^2-1),w)); if(p==1,print(lift(Mod(numerator(x),w))," ",lift(Mod(denominator(x),w)))); ); if(p==0,print(lift(Mod(numerator(x),w))," ",lift(Mod(denominator(x),w)))); if(Mod(numerator(x),w) == Mod(-S,w), printf("2^2^%d is prime !\n\n", n); , printf("2^2^%d is composite !\n\n", n); ) } ECPTF(4,1); for(n=2,10,ECPTF(n,0)); (with S=1 or S=-1 for Tsumura or Delomme) which generates the following result: Code: 9283 1 25064 1 26225 1 40394 1 3300 1 4079 1 1 1 2^2^4 is prime ! 1 1 2^2^2 is prime ! 1 1 2^2^3 is prime ! 1 1 2^2^4 is prime ! 422839282 1 2^2^5 is composite ! Now, changing only: - the seed: $\ \ \ \ \ \ \ \ \ \ \ \ \ x1 = 5 \ \longrightarrow \ 3$ , - the number of steps: $2^{n-1} \ \longrightarrow \ q-2$ , - the final test: $\ \ \ \ \ \ \ \equiv \pm 1 \ \longrightarrow \ \equiv \pm 2^{(q+1)/2} - 1$ - and the modulo: $\ \ \ \ F_n=2^{2^n}+1 \ \longrightarrow \ W_q = \frac{2^q+1}{3}$ I've got a PRP test for Wagstaff numbers: Code: S=-1; ECPTF(q,p)= { w=(2^q+1)/3; x1=3;x=x1; if(p>0,print("W",q,": ",w)); if(p>1,print("2^((q+1)/2): ",2^((q+1)/2))); for(i=2,q-2, x=S(Mod(x^4+2x^2+1,w)/Mod(4x(x^2-1),w)); if(p>0,printf("%3d %20d %20d\n",i,lift(Mod(numerator(x),w)),lift(Mod(-numerator(x),w)))); ); \\if(p==0,print(lift(Mod(numerator(x),w))," ",lift(Mod(denominator(x),w)))); if(lift(Mod(numerator(x),w)) == 2^((q+1)/2) - 1 \|\| lift(Mod(numerator(x),w)) == w - 2^((q+1)/2) - 1, printf("W%d is prime !\n", q) , if(p>0,printf("W%d is composite.\n", q)) ) } ECPTF(11,2); ECPTF(13,2); ECPTF(17,2) print(" "); forprime(q=19,15000,ECPTF(q,0)); generating: Code: W11: 683 2^((q+1)/2): 64 2 371 312 3 181 502 4 130 553 5 112 571 6 111 572 7 498 185 8 134 549 9 618 65 W11 is prime ! W13: 2731 2^((q+1)/2): 128 2 2161 570 3 2521 210 4 1210 1521 5 1233 1498 6 2351 380 7 829 1902 8 98 2633 9 2385 346 10 1139 1592 11 2602 129 W13 is prime ! (2602) W17: 43691 2^((q+1)/2): 512 2 20024 23667 3 39018 4673 4 4921 38770 5 17563 26128 6 30707 12984 7 37996 5695 8 25024 18667 9 20891 22800 10 6366 37325 11 30467 13224 12 19227 24464 13 25456 18235 14 15993 27698 15 511 43180 W17 is prime ! (511) W19 is prime ! W23 is prime ! W31 is prime ! W43 is prime ! W61 is prime ! W79 is prime ! W101 is prime ! W127 is prime ! W167 is prime ! W191 is prime ! W199 is prime ! W313 is prime ! W347 is prime ! W701 is prime ! W1709 is prime ! ... Which leads to a new conjectured PRP Test for Wagstaff numbers (Denomme-Savin-Tsumura-Reix): $x_0=3 \ , \ x_{j+1} = \frac{x_j^4+2x_j^2+1}{4(x_j^3-x_j)}$ $\text{If } \ x_{q-2} \ \equiv \ \pm \ 2^{(q+1)/2} - 1 \ \pmod{W_q} \ , \ \text{then } W_q = \frac{2^q+1}{3} \text{ is PRobably Prime} .$ (The sign on $2^{(q+1)/2}$ seems to depend on $q \ \pmod{12}$ : - minus when $\equiv 1 \text{ or } 11$ - plus when $\equiv 5 \text{ or } 7$ ) So, it is possible to keep the core of a "Primality Test using Elliptic Curve theory and designed for Fermat numbers" and build a PRP Test for Wagstaff numbers (which are close to Fermat numbers in some way). Weird! Now, the questions: - How to prove this PRP test? - Can we build a Primality Test with it? - Can we reuse Delomme/Savin/Tsumura method for proving this? or do we need something different? Last fiddled with by Dr Sardonicus on 2023-06-08 at 12:52 Reason: Per user's wish

2023-06-03, 14:42	#4
T.Rex Feb 2004 France 1665₈ Posts	Improved candidate PRP test Here is a second version which makes even more sens. First, consider this unique and simpler version of Denomme-Savin-Tsumura's primality test for Fermat numbers: $x_1=5 \ , \ 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 \ \pmod{F_n} \ , \ \text{then } F_n = 2^{2^n}+1 \text{ is prime} .$ With Pari/gp code: Code: ECPTF(n,p)= { q=2^n; w=2^q+1; x1=5;x=x1; for(i=2,q/2, x=Mod(x^4+2x^2+1,w)/Mod(4x(x^2-1),w); if(p==1,print(lift(Mod(numerator(x),w)))); ); if(p==0,print(lift(Mod(numerator(x),w)))); if(Mod(numerator(x),w) == Mod(-1,w), printf("2^2^%d is prime !\n\n", n); , printf("2^2^%d is composite !\n\n", n); ) } ECPTF(4,1); for(n=2,10,ECPTF(n,0)); This new version compares the final value of x with -1 . Now, with my candidate PRP test for Wagstaff numbers: The variable S (-1 or +1) has been removed. The number of steps has moved from q-2 to q-1. And the final test no more depends on q%12. MOREOVER, it makes MUCH more sens with the following! Denomme-Savin-Tsumura's primality test for $F_n=2^{2^n}+1$ compares the last value of x with -1. And now the last step of the new version of my candidate PRP test, since a Wagstaff number is 1/3* of a $2^q+1$ number, compares the last value of x with -1/3 !! Makes sens !!! Thus the changes from Denomme-Savin-Tsumura's primality test to my candidate PRP test are: - the seed: $\ \ \ \ \ \ \ \ \ \ \ \ \ x1 = 5 \ \longrightarrow \ 3$ , - the number of steps: $2^{n-1} \ \longrightarrow \ q-1$ , - the final test: $\ \ \ \ \ \ \ \equiv -1 \ \longrightarrow \ \equiv -1/3$ - and the modulo: $\ \ \ \ F_n=2^{2^n}+1 \ \longrightarrow \ W_q = \frac{2^q+1}{3}$ Code: ECPTF(q,p)= { w=(2^q+1)/3; x1=3;x=x1; if(p>0,print("W",q,": ",w)); if(p>1,print("-1/3: ",lift(Mod(-1/3,w)))); for(i=2,q-1, x=Mod(x^4+2x^2+1,w)/Mod(4x*(x^2-1),w); if(p>0,printf("%3d %20d\n",i,lift(Mod(numerator(x),w)))); ); if(lift(Mod(numerator(x),w)) == lift(Mod(-1/3,w)), printf("W%d is prime ! \n", q) , if(p>0,printf("W%d is composite.\n", q)) ) } ECPTF(11,2); ECPTF(13,2); ECPTF(17,2); print(" "); forprime(q=19,15000,ECPTF(q,0)); generating: Code: W11: 683 -1/3: 455 2 371 3 181 4 130 5 112 6 111 7 498 8 134 9 618 10 455 W11 is prime ! W13: 2731 -1/3: 910 2 570 3 2521 4 1521 5 1233 6 380 7 829 8 2633 9 2385 10 1592 11 2602 12 910 W13 is prime ! W17: 43691 -1/3: 29127 2 23667 3 39018 4 38770 5 17563 6 12984 7 37996 8 18667 9 20891 10 37325 11 30467 12 24464 13 25456 14 27698 15 511 16 29127 W17 is prime ! W19 is prime ! W23 is prime ! W31 is prime ! W43 is prime ! W61 is prime ! W79 is prime ! W101 is prime ! W127 is prime ! W167 is prime ! W191 is prime ! W199 is prime ! W313 is prime ! W347 is prime ! W701 is prime ! W1709 is prime ! W2617 is prime ! W3539 is prime ! W5807 is prime ! ... Which leads to a (probably final) new version of a conjectured PRP Test for Wagstaff numbers (Denomme-Savin-Tsumura-Reix): $x_1=3 \ , \ x_{j+1} = \frac{x_j^4+2x_j^2+1}{4(x_j^3-x_j)}$ $\text{If } \ x_{q-1} \ \equiv \ -1/3 \ \pmod{W_q} \ , \ \text{then } W_q = \frac{2^q+1}{3} \text{ is PRobably Prime} .<br />$ CQFD.

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

2023-06-03, 01:02	#2
Andrew Usher Dec 2022 3·13² Posts	You talk of this as a 'PRP test' here, which again is not a proof (https://mersenneforum.org/showthread.php?t=28305). Since we already have adequate PRP tests, a new one is not of practical importance. If you speculate this can be converted into a proof, you should be familiar with how this is done with the existing fast deterministic tests and why that approach doesn't work directly for Wagstaffs. Then you might get us somewhere, but the burden of proof is still on you.

2023-06-03, 05:55	#3
T.Rex Feb 2004 France 13×73 Posts	You are right. It's not a PRP test. It is a candidate PRP test. And we already have plenty of proved PRP tests for Wagstaff numbers, including two by myself, plus the Vrba-Reix test I contributed to a decade ago and which enabled me (as part of a team) to find the biggest Wagstaff PRP at that time. My goal is to reopen the area: study Elliptic Curves for Wagstaff numbers, which are not smooth, with a new information. I've started to learn Elliptic Curves (EC), and it is a jungle of complexity, and it will take me months (or years) to be able to understand them and then to master them. If you master them, please explain us where there are dark and unexplored places in the EC theory that could be used. I've started to discuss with some today experts of EC used for Primality Proving (PP), and they have started to look at more complex and different kinds of EC for PP for Wagstaff numbers. My experimental work only shows that a EC method for proving that a Fermat number is prime can be transformed into a possible PRP test for Wagstaff numbers. Showing that this candidate PRP test can be turned into a true PRP test seems possible, like it was possible to do this with Lucas-Lehmer Sequences theory (as I did several times) thought such theory cannot be used for proving a Primality Test for Wagstaff numbers. Now, is it impossible to turn this candidate PRP test into a primality proof ? I don't know yet. EC theory seems extremely rich and complex, and I'm not sure that all possibilities have been yet explored. And, if you are able to explain and prove that EC theory cannot be used for proving that a Wagstaff number is prime, please do: the burden of proof is on you. "They did'nt know it was impossible, so they did it".

2023-06-04, 23:46	#6
Andrew Usher Dec 2022 507₁₀ Posts	Sorry, I didn't realise who you were - you can ignore most of what I said as I'm sure you already know. I haven't investigated the mathematics of elliptic curves and I suppose there's some chance you might find something new - but there's many more skilled mathematicians that have. However, you did title this thread 'proving prime' when you admittedly have no idea how to even try doing that (obviously, standard ECPP is not what is meant here). No doubt you were inspired by the test for Fermats (again, not of practical importance), but as you state in summary, it seems all proposed fast elliptic-curve tests, like all conventional fast tests, require p+1 or p-1 to be factorable - and presumably for the same reason - and that's precisely the problem. ('Fast' tests are O(n^2) (like PRP) while ECPP is O(n^4), using the best techniques.) There seems no reason to doubt that the tests you're presenting here are valid PRP test (though slower than normal PRP), but equally no reason to think they might prove primality.

2023-06-08, 02:13	#11
mathwiz Mar 2019 2³×3²×5 Posts	It's probably best to just ignore Andrew Usher, whose posts generally seem to consist of nothing more than nitpicking/jabbing at others, and are entirely devoid of meaningful content.