¿Cómo podemos resolver $x^a = b \; mod \; n$ ecuación para n grande, a,

Question

Me gustaría tener un método para resolver una ecuación del tipo $x^a = b \; mod \; n$ sabiendo que n se puede descomponer en un producto de números primos $n = n_1 \times n_2 \times ... \times n_k$

Ya sé cómo hacerlo para números pequeños, como si n es un número primo:

en este caso, estoy buscando $e$ , de tal manera que $ae = 1 \; mod \; (n-1)$ . Así, puedo transformar mi ecuación en $x = b^e \; mod \; n$ .

Pero aquí los números son demasiado grandes para calcular esto de una sola vez. Así que tal vez hay un método para resolverlo que no conozco.

En mi ejercicio, he :

n = 264356242932330620591879762011459333409

b = 259252555055790712660181286804144327401

a = 151089236568313654499150506467499

Answer 1

El algoritmo euclidiano demuestra que $\gcd(b,n)=1$ .

Dado que se conoce la factorización primaria de $n$ , ya sabes $\phi(n)$ .

El algoritmo euclidiano demuestra que $\gcd(a,\phi(n))=1$ .

El algoritmo euclidiano ampliado da entonces $c$ tal que $ac \equiv 1 \bmod \phi(n)$ y así $x \equiv b^c$ .

Es probable que estos cálculos no sean fáciles si se hacen a mano. Pero WA lo maneja bien.