Re: question on finding square roots in a modulus

[Max Alekseyev <maxale@gmail.com>]

Just out of curiosity, are you trying to solve the challenge that Hermann posted here a while back?

https://github.com/Hermann-SW/RSA_numbers_factored/tree/main/1_sum_of_2_sqs_semiprime

Regards,

Max

On Sat, Nov 23, 2024 at 5:10 PM American Citizen <website.reader3@gmail.com> 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?

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