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 221How 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*17But how do we do this for -1 mod N where N is so huge we don't know its factors?
RandallP.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