Does halfgcd(sqrtm1,p) determine p=x^2+y^2 always with x>y>0 when applyi

hermann on Mon, 06 May 2024 12:11:59 +0200

Does halfgcd(sqrtm1,p) determine p=x^2+y^2 always with x>y>0 when applying abs() ?

To: pari-users@pari.math.u-bordeaux.fr
Subject: Does halfgcd(sqrtm1,p) determine p=x^2+y^2 always with x>y>0 when applying abs() ?
From: hermann@stamm-wilbrandt.de
Date: Mon, 06 May 2024 12:11:49 +0200
Authentication-results: secure-mailgate.com; auth=pass smtp.auth=93.90.177.40@web103.dogado.net
Delivery-date: Mon, 06 May 2024 12:11:59 +0200
User-agent: Roundcube Webmail/1.4.13



hermann@7950x:~$ gp -q

? sos(p,s=lift(sqrt(Mod(-1,p))))=[M,V]=halfgcd(s,p); abs([V[2],M[2,1]]);

? #
   timer = 1 (on)

?forprime(p=2,10^8,if(p%4==1,[x,y]=sos(p);if(p!=x^2+y^2||x<y,print(p))))

cpu time = 5,869 ms, real time = 5,870 ms.
? version()
[2, 16, 1]
?


Regards,

Hermann.