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

[Kurt Foster <drsardonicus@earthlink.net>]

On Nov 15, 2024, at 2:28 PM, hermann@stamm-wilbrandt.de wrote:

> Recently new biggest known prime (41,024,320 decimal digits) M_52  
> was found.
>
> It turned out that for all Mersenne primes but M_1, -3 is a  
> quadratic residue.
> Therefore there are integers x,y with M_52=x^2+3*y^2.

OK, here we go!

We have p = 136279841 == 5 (mod 22), so 2^p - 1 = M == 2^5 - 1 == 8  
(mod 23).  Now (8/23) = (2/23) = +1, and M == 3 (mod 4) so by  
quadratic reciprocity

(-23/M) = (M/23) = +1. That is, -23 is a quadratic residue (mod M).   
Using the usual formula, we have that

(-23)^((M+1)/4) is a square root of -23 (mod M). [Since (M+1)/4 is  
even (in fact, a power of 2), we can take 23^((M+1)/4) instead.]

However, this does NOT insure that M = x^2 + 23*y^2.  One possible way  
to test the question is to compute a square root of -23 (mod M) and  
use halfgcd (Cornacchia algorithm) and see whether it produces a  
solution.

In any case, the prime M splits into two prime ideals in  
Q(sqrt(-23)).  If M = x^2 + 23*y^2 the ideals are principal; otherwise  
not.