mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2023-06-08, 12:53   #12
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

3×7×311 Posts
Default

Quote:
Originally Posted by T.Rex View Post
<snip>
"Elliptic Curves for Proving that a Wagstaff number is prime" : I should have added a question mark at the end, yes.
<snip>
Done!
Dr Sardonicus is offline   Reply With Quote
Old 2023-06-09, 20:54   #13
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

13·73 Posts
Default

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
T.Rex is offline   Reply With Quote
Old 2023-06-09, 21:51   #14
R.D. Silverman
 
R.D. Silverman's Avatar
 
"Bob Silverman"
Nov 2003
North of Boston

1DD216 Posts
Default

Quote:
Originally Posted by T.Rex View Post
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?
R.D. Silverman is offline   Reply With Quote
Old 2023-06-10, 01:01   #15
Andrew Usher
 
Dec 2022

2·3·7·13 Posts
Default

Quote:
Originally Posted by T.Rex View Post
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.
Andrew Usher is offline   Reply With Quote
Old 2023-06-10, 10:53   #16
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

16658 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
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
T.Rex is offline   Reply With Quote
Old 2023-06-10, 11:14   #17
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

13·73 Posts
Default

Quote:
Originally Posted by Andrew Usher View Post
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 is offline   Reply With Quote
Old 2023-06-14, 13:28   #18
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

13·73 Posts
Default

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 is offline   Reply With Quote
Old 2023-06-14, 19:19   #19
T.Rex
 
T.Rex's Avatar
 
Feb 2004
France

13·73 Posts
Default

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 .
T.Rex is offline   Reply With Quote
Reply

Thread Tools


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

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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2023, 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.

โ‰  ยฑ โˆ“ รท ร— ยท โˆ’ โˆš โ€ฐ โŠ— โŠ• โŠ– โŠ˜ โŠ™ โ‰ค โ‰ฅ โ‰ฆ โ‰ง โ‰จ โ‰ฉ โ‰บ โ‰ป โ‰ผ โ‰ฝ โŠ โŠ โŠ‘ โŠ’ ยฒ ยณ ยฐ
โˆ  โˆŸ ยฐ โ‰… ~ โ€– โŸ‚ โซ›
โ‰ก โ‰œ โ‰ˆ โˆ โˆž โ‰ช โ‰ซ โŒŠโŒ‹ โŒˆโŒ‰ โˆ˜ โˆ โˆ โˆ‘ โˆง โˆจ โˆฉ โˆช โจ€ โŠ• โŠ— ๐–• ๐–– ๐–— โŠฒ โŠณ
โˆ… โˆ– โˆ โ†ฆ โ†ฃ โˆฉ โˆช โŠ† โŠ‚ โŠ„ โŠŠ โŠ‡ โŠƒ โŠ… โŠ‹ โŠ– โˆˆ โˆ‰ โˆ‹ โˆŒ โ„• โ„ค โ„š โ„ โ„‚ โ„ต โ„ถ โ„ท โ„ธ ๐“Ÿ
ยฌ โˆจ โˆง โŠ• โ†’ โ† โ‡’ โ‡ โ‡” โˆ€ โˆƒ โˆ„ โˆด โˆต โŠค โŠฅ โŠข โŠจ โซค โŠฃ โ€ฆ โ‹ฏ โ‹ฎ โ‹ฐ โ‹ฑ
โˆซ โˆฌ โˆญ โˆฎ โˆฏ โˆฐ โˆ‡ โˆ† ฮด โˆ‚ โ„ฑ โ„’ โ„“
๐›ข๐›ผ ๐›ฃ๐›ฝ ๐›ค๐›พ ๐›ฅ๐›ฟ ๐›ฆ๐œ€๐œ– ๐›ง๐œ ๐›จ๐œ‚ ๐›ฉ๐œƒ๐œ— ๐›ช๐œ„ ๐›ซ๐œ… ๐›ฌ๐œ† ๐›ญ๐œ‡ ๐›ฎ๐œˆ ๐›ฏ๐œ‰ ๐›ฐ๐œŠ ๐›ฑ๐œ‹ ๐›ฒ๐œŒ ๐›ด๐œŽ๐œ ๐›ต๐œ ๐›ถ๐œ ๐›ท๐œ™๐œ‘ ๐›ธ๐œ’ ๐›น๐œ“ ๐›บ๐œ”