How can we solve $x^a = b \; mod \; n$ equation for big n, a,

Question

I would like to have a method to solve an equation of the type: $x^a = b \; mod \; n$, knowing that n can be decomposed into a product of prime numbers $n = n_1 \times n_2 \times ... \times n_k$

I already know how to do it for small numbers, like if n is a prime number:

in this case, I am looking for $e$, such that $ae = 1 \; mod \; (n-1)$. Like that, I can transform my equation into $x = b^e \; mod \; n$.

But here the numbers are too big to compute this in a single time. So maybe there is a method to solve it I am not aware of.

In my exercise, I have :

n = 264356242932330620591879762011459333409

b = 259252555055790712660181286804144327401

a = 151089236568313654499150506467499

Answer 1

The Euclidean algorithm proves that $\gcd(b,n)=1$.

Since you know the prime factorization of $n$, you know $\phi(n)$.

The Euclidean algorithm proves that $\gcd(a,\phi(n))=1$.

The extended Euclidean algorithm then gives $c$ such that $ac \equiv 1 \bmod \phi(n)$ and so $x \equiv b^c$.

These computations are probably not easy when done by hand. But WA handles it fine.