# 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.

• I presume that choosing $b=c$ and $a=(n-1)!+1$ is cheating? Mar 3 '20 at 10:37
• From your examples, it looks like you are insisting on $a<n$ and $b<n$. Perhaps you should state your restrictions explicitly. Mar 3 '20 at 11:22
• $b<n$ is without loss of generality. And an exponentially large $a$ will require an exponential-time algorithm, which does not count as efficient. If there is a polynomial-time algorithm (possibly randomized), that by itself imposes a bound $a\le2^{(\log n)^k}$ for some constant $k$. Mar 3 '20 at 12:01
• @JeremyRickard: Not cheating, but it's not admissible as no efficient algorithm can output such a large number. See Emil's comment for further description. Mar 3 '20 at 13:56
• @GerryMyerson: As per Emil's comment, it might be unnecessary, though I edited the question to reflect the conditions. Mar 3 '20 at 14:04

After much struggling, I found out that this is currently deemed a hard problem; so there is no known efficient algorithm to solve it.

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:

1. 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.

$$~$$

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

$$~$$

1. 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.