Raíz cuadrada algoritmo en el modulo $n = pq$

Question

He estado atrapado en este problema un poco.

Tengo que encontrar un algoritmo eficiente que, dado que: $$ p = 4k+3\\ q = 4m+3\\ p,q \hspace{2 mm} \text{impares primos}\\ un\in \mathbb{N} $$

comprueba si existe alguna$\ b$ de manera tal que, $$ b^2 \equiv\pmod n,\quad n=pq,\quad b\in \mathbb{N} $$

Algo útil podría ser la siguiente propiedad, que ya ha sido comprobada: $$ b^2 \equiv\pmod n,\hspace{2 mm} n=pq \Leftrightarrow c^2 \equiv\pmod q \wedge d^2 \equiv\pmod p $$

pero no estoy muy seguro de cómo utilizar esa información.

Todos mis planteamientos han sido unsuccesful y no he sido capaz de utilizar el hecho de que $\ p$ $\ q$ tiene una determinada forma de$\ (4k + 3)$.

Toda la ayuda es apreciada.

Answer 1

Sugerencia: Si utiliza Euler Criterio sugerido por André Nicolas y encontrar que $a$ tiene raíces cuadradas mod p, sabes que $a^{\frac{p-1}{2}} \equiv 1 \pmod p$. Ahora establezca $r := a^{\frac{p+1}{4}} \pmod p$, y calcular el $r^2 \pmod p$. Para ello se utiliza el hecho de que $p=4 k + 3$ y es eficaz si usted tiene un eficaz algoritmo de exponenciación modular. Si $a$ tiene raíces cuadradas mod $p$$q$, a continuación, utilizar el teorema del resto Chino para obtener raíces cuadradas mod $n$.