Re: question on finding square roots in a modulus

[Kurt Foster <drsardonicus@earthlink.net>]

On Nov 23, 2024, at 4:03 PM, American Citizen wrote:

> Hello all:
>
> Suppose I have
>
> Mod(-1,221) = Mod(220,221)
>
> When I try to take the square root
>
> sqrt(Mod(220,221))
>
> The command blows up since 221 is NOT prime number.
>
> >   ***   at top-level: sqrt(Mod(220,221))
> >   ***                 ^------------------
> >   *** sqrt: not a prime number in sqrt [modulus]: 221.
> >   ***   Break loop: type 'break' to go back to GP prompt
>
> 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 ?
>
> I actually did this by hand: the following values work: 21 mod 221,   
> 47 mod 221,  174 mod 221, and 200 mod 221
>
> Btw: 221 = 13*17
>
> But how do we do this for -1 mod N where N is so huge we don't know  
> its factors?

The short answer is, "You don't."  Anything beyond an equal and  
opposite pair of square roots of -1 (or of anything else) (mod N) give  
you a factorization of N.

If you know x and y (mod N) such that x^2 == a (mod N), y^2 == a (mod  
N) but x <>y (mod N) and x<> -y (mod N), then from

x^2 - y^2 == 0 (mod N) we have that

gcd(x-y,N)*gcd(x+y,N) is a proper factorization of N.