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

[hermann@stamm-wilbrandt.de]

On 2024-11-17 18:29, Bill Allombert wrote:
> > And for M_18..M_38 with -23 being quadratic residue with automation, 
> > below.
> >
> > For all 18 primes sqrt(Mod(-23,p)) got computed and verified, not a 
> > single
> > exception ...
>
> Even if the squareroot exists, the equation M = a^2+23*b^2 might not
> have a solution.
Thank you, I verified that for the manually tested Mersenne prime 
exponents
below 1000 the equations do not exists, here with gcd(s+I,p)==1.

For the bigger numbers I used halfgcd() to verify because gcd() was too 
slow:

hermann@7950x:~/llr405src/linux64llr$ tail -3 crea2
echo -e ";\nMod(s,p)^2==Mod(-23,p)"
echo "[M,V]=halfgcd(lift(s),p);[x,y]=[V[2],M[2,1]];"
echo "x^2+23*y^2==p"
hermann@7950x:~/llr405src/linux64llr$


Only p=2^4423-1 and p=2^216091-1 have a representation with integers x,y
as p==x^2+23*y^2.

> However in that case the equation M = 2*a^2+a*b+3*b^2 must have a 
> solution!
Any literature pointer, or how to determine a,b in that case?


Regards,

Hermann.