Given $n, c$ find $a>1,b$ such that $b ^ a \equiv c \pmod n$ 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.

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, and is known to be hard. If $a$ is fixed, the problem might be a variant of RSA or Rabin 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.

 A: 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):

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:


  
*Barić N, Pfitzmann B (1997) Collision-free accumulators and
  fail-stop signature schemes without trees. In: Fumy W (ed)
  Advances in cryptology – EUROCRYPT’97. Lecture notes in
  computer science, vol 1233. Springer, Berlin, pp 480–494.
  

$~$


  
*Cramer R, Shoup V (2000) Signature schemes based on the
  strong RSA assumption. ACM Trans Inform Syst Sec 3(3):
  161–185.
  

$~$


  
*Fujisaki E, Okamoto T (1997) Statistical zero knowledge protocols to prove modular polynomial relations. In: Kaliski BS
  Jr (ed) Advances in cryptology – CRYPTO’97. Lecture notes in
  computer science, vol 1294. Springer, Berlin, pp 16–30.
  

