American Citizen on Sat, 23 Nov 2024 23:03:54 +0100


[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

question on finding square roots in a modulus


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?

Randall

P.S: this problem is relating to factoring numbers N = p1*p2 where p1 and p2 are primes congruent to 1 mod 4 but we only know one pair x^2 + y^2 = N