Resolver para $x$ en $x^k \equiv b \pmod n$ où $n$ no es primo y $\gcd(k, \phi(n)) > 1$

Question

¿Cómo se resuelve para $x$ en

$x^k \equiv b \pmod n$

donde $n$ no es primo y $\gcd(k,\phi(n)) > 1$

¿Se puede hacer esto utilizando el teorema de Euler y la función totiente?

Answer 1

La respuesta es probablemente no. Incluso para la congruencia más simple
$$ x^2 \equiv b \pmod{p} $$ con $p$ primo no conozco ninguna forma directa de resolverlo salvo en casos excepcionales (Aunque hay algoritmos probabilísticos rápidos para encontrarlo como el de Tonnelli y Shank y también el algoritmo de Schoof que funciona en tiempo polinomial determinista). Para resolver tu congruencia yo haría lo siguiente:

Supongo que $\gcd(b,n)=1$ . Sea $d = \gcd(k,n)$ y encontrar $u,v$ tal que $uk + v\phi(n) = d$ . potenciando la congruencia a la $u$ -enésima potencia obtenemos la congruencia $$ x^d \equiv b^u \pmod{n} $$ ahora si $b^{u\phi(n)/d} \not \equiv 1 \pmod{n}$ entonces sabes que no hay solución (porque el lado izquierdo es $\equiv 1 \pmod{n}$ .

Si $b^{u\phi(n)/d} \equiv 1 \pmod{n}$ entonces no está seguro de si hay soluciones o no. Para comprobarlo debes tener en cuenta $n$ como producto de potencias primarias, $n = \prod p^t$ .

Ahora, hay soluciones a la congruencia original si y sólo si para cada factor de potencia primo $p^t$ de $n$ tenemos $$ b^{u \phi(p^t)/d'} \equiv 1 \pmod{ p^t} \quad \text{with } d' = \gcd(d,\phi(p^t)) $$ si alguna de estas congruencias falla entonces no hay soluciones.

El problema se reduce a encontrar soluciones a cada congruencia $$ x^d \equiv b^u \pmod{p^t} $$ y luego combinarlos usando el teorema del recordatorio chino.

Usando el mismo argumento que antes podemos reducir esto a la congruencia $$ x^{d'} \equiv b' \pmod{p^t} \quad\text{ for certain }b'\text{ with }\quad b^{\phi(p^t)/d'} \equiv 1 \pmod{p^t}$$

En el caso afirmativo entonces la congruencia $$ x^{d'} \equiv b' \pmod{p^t} $$ tiene exactamente $d'$ soluciones, es decir, el polinomio $P(x) = x^{d'} - b'$ es el producto de $d'$ factores lineales, no conozco ningún algoritmo que factorice módulo $p^t$ en tiempo polinómico garantizado, pero hay formas probabilísticas rápidas de resolverlo, por ejemplo, se puede calcular el polinomio $\gcd$ utilizando varios valores aleatorios $a$ no divisible por $p$ : $$ \gcd( (x+a)^{\phi(p^t)/d'}-1, P(x) ) $$ y utilizando los resultados para descomponer recursivamente el polinomio $P(x)$ en otras más pequeñas hasta conseguir los factores lineales.