$pq\equiv 1\pmod 4$ Cómo encontrar $p,q\bmod 4$ ?

Question

Alguien me ha hecho una pregunta, no tengo ni idea, la pregunta es:

Si un número entero positivo $n\equiv 1\pmod 4$ es el producto de dos primos, (denota $n=pq,$ como un RSA número) pero no sabemos qué $p,q$ es, podemos encontrar si $p,q\equiv 1\pmod 4$ o $p,q\equiv -1\pmod 4$ ¿Rápido?

Editar: Para que este problema quede más claro, me gustaría ilustrarlo con un ejemplo:

Dado $n=54106525115786488721104110650095154684919808365060517563123199931159\\ 571762703975072565387621847347234678280888429084887681391085492532589162\\ 3649321540843857479706239369353295580392388377=pq,$

¿Puedes encontrar $p\pmod 4$ y $q\pmod 4$ en menos de una hora por ordenador?

Answer 1

$p,q\equiv 1\pmod 4$ si y sólo si la congruencia $x^2\equiv -1\pmod{pq}, x\in\mathbb Z$ es solucionable.

Debido al primer complemento de la reciprocidad cuadrática, esto es válido para las congruencias $$x_1^2\equiv -1\pmod p\\x_2^2\equiv -1\pmod q$$ por separado. Como $x_1$ y $x_2$ sólo están definidos hasta un múltiplo de p y q respectivamente, una solución simultánea es posible siempre que ambas congruencias sean resolubles (por el teorema del resto chino).