Given a natural number $n$ (of **unknown** factorization) and an arbitrary number $c \in \mathbb{Z}^\*\_n$ (the set of natural numbers smaller than $n$ and coprime to it), is there an **efficient** algorithm which outputs numbers $a \in \{2,\ldots,n-1\}$ and $b \in \mathbb{Z}^\*\_n$ such that:


$$b ^ a \equiv c \pmod n$$



> 
> **Note 1:** In my problem, $n$ is the product of two [safe primes](https://en.wikipedia.org/wiki/Safe_prime).
> 
> 
> 


**Example:** Let $n=77$ and $c=2$. The set of all admissible pairs $(b,a)$ is:


$$\{ (18, 23), (30, 7), (39, 29), (46, 11), (51, 13), (72, 19), (74, 17) \} \,.$$


For the same $n$ and $c=15$, the set of all admissible pairs $(b,a)$ is:


$$\{ (2, 12), (3, 24), (4, 6), (5, 18), (6, 8), (8, 4), (9, 12), (13, 2), (16, 3), (17, 18), (18, 6), (19, 24), (20, 2), (24, 12), (25, 9), (26, 6), (27, 8), (29, 6), (30, 24), (31, 12), (36, 4), (37, 6), (38, 18), (39, 18), (40, 6), (41, 4), (46, 12), (47, 24), (48, 6), (50, 8), (51, 6), (52, 24), (53, 12), (57, 2), (58, 9), (59, 6), (60, 3), (61, 18), (62, 6), (64, 2), (68, 12), (69, 4), (71, 3), (72, 18), (73, 6), (74, 24), (75, 12) \} \,.$$



> 
> **Note 2:** One can assume that $c$ is chosen randomly, and the algorithm is probabilistic and may output the right answer with good probability.
> 
> 
> 


$~$



> 
> **Note 3:** If $b$ is fixed, the problem is the [discrete log](https://en.wikipedia.org/wiki/Discrete_logarithm), and is known to be hard. If $a$ is fixed, the problem might be a variant of [RSA](https://en.wikipedia.org/wiki/RSA_(cryptosystem)) or [Rabin](https://en.wikipedia.org/wiki/Rabin_cryptosystem) cryptosystem, both of which are considered hard. I hope that by giving the algorithm the freedom of picking both $a,b$, it is solvable efficiently.
> 
> 
> 



Given $n, c$ find $a>1,b$ such that $b ^ a \equiv c \pmod n$
After much struggling, I found out that this is currently deemed a hard problem; so there is no known efficient algorithm to solve it.


From the [Encyclopedia of Cryptography and Security (2011)](https://link.springer.com/referencework/10.1007/978-1-4419-5906-5):



> 
> **Strong RSA Assumption**
> 
> 
> The Strong RSA Assumption was introduced by Baric
>  and Pfitzmann [3] and by Fujisaki and Okamoto [18] (see
>  also [13]).
> 
> 
> This assumption differs from the RSA Assumption in
>  that the adversary can select the public exponent e. The
>  adversary’s task is to compute, given a modulus n and a
>  ciphertext C, any plaintext M and (odd) public exponent
>  e ≥ 3 such that $C = M^e \pmod n$. This may well be easier
>  than solving the RSA Problem, so the assumption that it is
>  hard is a stronger assumption than the RSA Assumption.
>  The Strong RSA Assumption is the basis for a variety of
>  cryptographic constructions.
> 
> 
> 


with references as follows:



> 
> 3. Barić N, Pfitzmann B (1997) [Collision-free accumulators and
>  fail-stop signature schemes without trees](https://link.springer.com/content/pdf/10.1007/3-540-69053-0_33.pdf). In: Fumy W (ed)
>  Advances in cryptology – EUROCRYPT’97. Lecture notes in
>  computer science, vol 1233. Springer, Berlin, pp 480–494.
> 
> 
> 


$~$



> 
> 13. Cramer R, Shoup V (2000) [Signature schemes based on the
>  strong RSA assumption](https://dl.acm.org/doi/10.1145/357830.357847). ACM Trans Inform Syst Sec 3(3):
>  161–185.
> 
> 
> 


$~$



> 
> 18. Fujisaki E, Okamoto T (1997) [Statistical zero knowledge protocols to prove modular polynomial relations](https://link.springer.com/content/pdf/10.1007%2FBFb0052225.pdf). In: Kaliski BS
>  Jr (ed) Advances in cryptology – CRYPTO’97. Lecture notes in
>  computer science, vol 1294. Springer, Berlin, pp 16–30.
> 
> 
> 


