# Modular equation system

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

• Reformulate as $A\cdot B^{-1} = q^k \pmod N$, though not all $B$s can have inverse in $\bmod N$. Jan 25, 2021 at 16:37
• @kelalaka: if $B$ does not have an inverse (and is not 0), then that in itself will allow you to factor $N$ Jan 25, 2021 at 16:55

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$$
• Maybe this is more clear? $A = B \cdot q^k + N \cdot t$ then take modulo $t$ then $A = 0 \bmod q$ Jan 25, 2021 at 19:40