Reversible modular exponent in cryptography

Question

I know this is possible from working code, but I can't wrap my head around how.

For the given equation:

$b = x^p\bmod\text{public_key}$

Where $p$ is prime ($131$ in my case).

How to compute a public_key such that $x$ can be solved?

Answer 1

Given prime $q$ such that $q-1 \mod p \ne 0$, to solve $b = x^p \mod q$, let $s = p^{-1} \mod (q-1)$ (this can be obtained using the Euclidean algorithm). Then $b^s = x^{ps} = x \mod q$. If your public key is the product of known primes $q_i$ such that $q_i-1 \mod p \ne 0$, do this for each of the primes $q_i$, and then use the Chinese Remainder Theorem.