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

[Bill Allombert <Bill.Allombert@math.u-bordeaux.fr>]

On Sun, Nov 17, 2024 at 08:01:49PM +0100, hermann@stamm-wilbrandt.de wrote:
> 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?

This is what qfbsolve does:
- Find b and c so that -23 = b^2-4*p*c (so b = sqrt(-23 mod p) etc.)
- Compute qfbredsl2(Qfb(p,b,c))
This gives you [Q,M] then (M^-1)[,1] is a solution of Q.

Q depends on the choice of the square root, but in that case it
will be either Qfb(2,-1,3) or Qfb(2,1,3).

Cheers,
Bill.