2
$\begingroup$

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

$\endgroup$

1 Answer 1

6
$\begingroup$

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)$.

$\endgroup$
2
  • 1
    $\begingroup$ 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$. $\endgroup$
    – fgrieu
    Sep 6, 2022 at 11:40
  • 1
    $\begingroup$ 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. $\endgroup$ Sep 6, 2022 at 16:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.