Re: PARI/GP timings for operations on biggest known 41,024,320 decimal digit prime

[hermann@stamm-wilbrandt.de]

On 2024-11-16 12:32, tony.reix@laposte.net wrote:
> BTW, do you know that Mersenne numbers can also be written as:
>    M_q=(8x)^2-(3qy)^2
> ?
> Once if M_q is prime (and x & y are obvious). Several times if M_q is
> composite (and x & y are not obvious at all).
Interesting, the questions you had regarding this were answered by Bill.

> Do you have a link to a paper clarifying the property of M_q as
> x^2+3y^2 ?
First, for me M_n is the n-th Mersenne prime, and not 2^n-1.

All known 52 Mersenne primes but M_1 have -3 as quadratic residue:
https://gist.github.com/Hermann-SW/f44c3500b8db158eb87ae8c2fd010e21

hermann@7950x:~$ gp -q mpe.gp
? #mpe
52
? foreach(mpe,e,print1(kronecker(-3,2^e-1)))
0111111111111111111111111111111111111111111111111111
? mpe[52]
136279841
?

So there exists s for M_n such that s^2 + 3 * 1^2 == M_n.

gcd(M_n, s+I) results in x+I*y with norml2()==M_n.

Since gcd() is too slow (I stopped after 2h on AMD 7950X CPU)
computation with halfgcd() was done in 17 seconds for M_52:

[M,V]=halfgcd(s,p);[x,y]=[V[2],M[2, 1]];


sqrt(Mod(-3,M_52)) was determined with gwnum lib based LLR software on 
7950X CPU with 1580% CPU in 8.01 days. On same CPU determination of sum 
of two squares for top 10 known primes =1 (mod 4) did never take 7h ...

https://github.com/Hermann-SW/top10.sum_of_2_squares.primes?tab=readme-ov-file#runtimes


> Do you see for M_52 than x is even and y is a multiple of 3 ?
Yes, I appended two lines:

hermann@7950x:~/llr405src/linux64llr$ tail -4 
M_52.is.x^2_plus_3_times_y^2.hex.gp
p==x^2+3*y^2
##
Mod(x,2)
Mod(y,3)
hermann@7950x:~/llr405src/linux64llr$ gp -q < 
M_52.is.x^2_plus_3_times_y^2.hex.gp
  ***   last result computed in 5 ms.
  ***   last result computed in 82 ms.
  ***   last result computed in 82 ms.
1
  ***   last result computed in 390 ms.
Mod(0, 2)
Mod(0, 3)
hermann@7950x:~/llr405src/linux64llr$

I added M_52.is.x^2_plus_3_times_y^2.hex.gp to the gist where x,y are
stored as hexadecimal numbers. That resulted in 13x speedup of both 
lines.


Regards,

Hermann.