I have $N=p\cdot q$ and the following system where I know $A,B,C,D, k$:
$$A = B \cdot q^k \pmod N$$
and
$$C = D \cdot p^k \pmod N$$
Is there an easy way to recover $p$ and $q$?
$\begingroup$
$\endgroup$
2
-
$\begingroup$ Reformulate as $A\cdot B^{-1} = q^k \pmod N$, though not all $B$s can have inverse in $\bmod N$. $\endgroup$– kelalakaCommented Jan 25, 2021 at 16:37
-
$\begingroup$ @kelalaka: if $B$ does not have an inverse (and is not 0), then that in itself will allow you to factor $N$ $\endgroup$– ponchoCommented Jan 25, 2021 at 16:55
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
Is there an easy way to recover $p$ and $q$?
Yes (in all cases except for $B, D$ are both multiples of $N$, or $k=0$, and assuming that $p, q$ are distinct primes)
Let us assume that $B$ is not a multiple of $N=pq$; then:
If $B$ is not a multiple of $p$, then $\gcd(A, N) = q$ (because $A=Bq^k$ is a multiple of $q$ but not $p$); simple division also recovers $p$
If $B$ is a multiple of $p$, then it is not a multiple of $q$ (by assumption); in that case $\gcd(B, N) = p$
-
$\begingroup$ Maybe this is more clear? $A = B \cdot q^k + N \cdot t$ then take modulo $t$ then $A = 0 \bmod q$ $\endgroup$– kelalakaCommented Jan 25, 2021 at 19:40