# Factoring RSA if prime p is used as the private exponent

I've got two 1024 bits primes $$p,q$$, and $$n = p \cdot q$$. Now I know the result of $$c^{p} \bmod n = x$$, also the value of $$c$$ is given, I wonder if it is possible to factorize $$n$$.

From Fermat's little theorem we know $$a^p \equiv a \pmod{p}\,.$$ Applying this to the present problem, $$c^p \equiv c \equiv x \pmod{p}$$, and thus with high probability $$p = \gcd(x - c, n)$$.
• The conclusion "thus $p=\gcd(x-c,n)$" is unwarranted. That's overwhelmingly likely for random $c$. Baring this, sure $p$ divides $x-c$, but it can happen that $x\equiv c\pmod n$, in which case $\gcd(x-c,n)$ is $n$ and does not reveal a factorization of $n$. In that case, it's worth trying if $\gcd(c,n)$ is a non-trivial factor of $n$, but that's not certain either. Small example: take $p=109$, $q=211$. Now $x\equiv c\pmod n$ occurs for $763$ values of $c\in[0,n)$, that is probability $7/q>3.3\%$ for random $c$. Within these only $114$, that is $<15\%$, are such that $\gcd(c,n)$ is $p$ or $q$.
• Point well taken. This happens when $p \bmod \mathrm{ord}_q(x) \in {0,1}$. The other 114 aren't really valid elements of $\mathbb{Z}_n^\ast$, since they are multiples of $p$ or $q$ and amount to guessing one of the factors. Sep 6, 2022 at 16:03