# Is it a variant of Strong RSA assumption?

Informally, the hardness of RSA/Strong RSA assumption lies in the hardness of factoring a large composite number $N$ having two large primes as its factors. If RSA modulus $N$ is a prime number, then the system is trivially breakable.

But, what about this variant of the Strong RSA problem presented in Ben Lynn's PhD dissertation? Here it says, given $c$, it's hard to find a pair $(g,a)$ such that $c = g^a$. RSA modulus $N$ hasn't been talked about here.

Are the above two notions synonymous?

• What about just outputting $\:(c,\hspace{-0.04 in}1)\;$? $\;\;\;\;$ – user991 Jan 26 '15 at 11:46
• @RickyDemer That actually seems to be an error in Ben Lynn's PhD thesis: It talks about $a$ being chosen from $\mathbb Z_{r-1}^+$, which includes $1$. Therefore, the "strong RSA problem" as defined in the thesis is trivial. Do I miss something here? – yyyyyyy Jan 26 '15 at 11:49

The modulus $N$ is implicit in the group $\mathbb Z_N^\ast$ that $c$ and $g$ are chosen from. That is, in this context, $g^a$ is taken to mean "the residue class represented by $x^a\bmod N$ where $x$ denotes some representant of $g$'s residue class".
Therefore, when additionally requiring that $a\geq3$ and odd, this notion is equivalent to the strong RSA assumption as defined in Rivest's paper.