Re: question on finding square roots in a modulus

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

On Sat, Nov 23, 2024 at 02:03:47PM -0800, American Citizen wrote:
> However, if we tinker around we find that
> 
> (Mod(174,221)^2) = Mod(220,221)
> 
> so 174 mod 221 is a valid square root of 220 mod 221 or -1 mod 221
> 
> How can we quickly find all modulus  values 221, such that their square is
> congruent to -1 mod 221 ?

This is a very good question. The most reliable solution is to use Zn_quad_roots

install(Zn_quad_roots,GGG)
isNULL(z=[])=z;
znquadroots(a,F=factor(a.mod))=
{ 
  my(V=isNULL(Zn_quad_roots(F,0,lift(-a))));
  if(#V,Mod(V[2],V[1]),V);
}
znquadroots(Mod(-1,221))
%4 = [Mod(21,221),Mod(174,221),Mod(47,221),Mod(200,221)]

We really need to add this to GP proper.
In C there is also a static function 'polrootsmodpn' that we could use.

Cheers,
Bill.