Given four numbers $(a,b,e,n)$ is it possible to find $k$ such that $k^{e}a = b \pmod n$?

Question

Let $n$ be a large given number. Also, $n = pq$ for some unknown primes $p,q$.

The Euler Totient function, $\varphi(n) = (p-1)(q-1)$ is not known or easy to calculate. $e$ is a given number co-prime to $\varphi(n)$.

This is essentially the RSA cryptographic scheme.

Now, given any two numbers $a,b$ such that $a<n,b<n$, I am interested in an integer $k$ which satisfies $$k^ea \equiv b \pmod{n}$$

If such a scenario is possible, am I right in thinking that the scheme can be cracked if I know the encoded and decoded messages for just one number($b$ in this case)?
I know that such $k$ doesn't exist for all $a,b$. For example, there is no solution to $2k^2 = 3 \pmod{10}$. So, I would like to know more about the following

1. Under what condition does such a $k$ exist for any $(a,b,e,n)$?
2. If it does not, is there any probability or bounds? For example, $k$ exists only for $25\%$ $ (a,b)$ pairs.
3. In case such a $k$ exists, is it possible to calculate it 'efficiently'?

Any other relevant information about '$k$' will be equally appreciated.

I had asked a similar question which was answered. But I am unable to relate the two cases.

Thanks in advance !

Answer 1

This time you'll do the same and obtain $k^{e} \equiv b.a^{-1} \pmod{n}$ as before. Now, you have to know whether $k^{e} \equiv b.a^{-1} \pmod{n}$ has a solution or not. Unfortunately, it happens that this is not always the case.

However, we have the following theorems in elementary number theory that assume you already know about primitive roots:

Theorem: Suppose that $p$ is a prime number and $x$ is an integer such that $\gcd(x,p)=1$. If $g$ is a primitive root of $p$ and $a \equiv g^{m} \pmod{p}$ then $x^n \equiv a \pmod{p}$ has a solution if and only if $\gcd(n,p-1) \mid m$.

Another related theorem is this one:

Theorem: Suppose that $p$ is a prime number and $x$ is an integer such that $\gcd(a,p)=1$. Then the congruence equation $x^{n} \equiv a \pmod{p}$ has a solution if and only if $$ a^{\frac{p-1}{d}} \equiv 1 \pmod{p}$$

Where $d= \gcd(n,p-1)$.

These are powerful theorems to guarantee the existence of the solution to the equation $x^{n} \equiv a \pmod{n}$. They guarantee the existence, but to calculate the $x$ such that $x^n \equiv a \pmod{n}$ you have to know about primitive roots and indices (discrete logarithms) and I'm afraid that there is no elementary known solution to this problem that enables you to calculate discrete logarithms directly with an algorithm.

Note that it suffices to solve the problem when the modulus is prime. Because if you know the solutions for prime moduli you can apply Chinese remainder theorem to find the solution for the case $n=pq$.