模方程系統

我有 $ N=p\cdot q $ 以及我知道的以下系統 $ A,B,C,D, k $ :

$$ A = B \cdot q^k \pmod N $$

和

$$ C = D \cdot p^k \pmod N $$

有沒有簡單的恢復方法 $ p $ 和 $ q $ ?

有沒有簡單的恢復方法 $ p $ 和 $ q $ ?

是（在所有情況下，除了 $ B, D $ 都是的倍數 $ N $ ， 或者 $ k=0 $ ，並假設 $ p, q $ 是不同的素數）

讓我們假設 $ B $ 不是的倍數 $ N=pq $ ; 然後：

• 如果 $ B $ 不是的倍數 $ p $ ， 然後 $ \gcd(A, N) = q $ （因為 $ A=Bq^k $ 是的倍數 $ q $ 但不是 $ p $ ); 簡單除法也恢復 $ p $
• 如果 $ B $ 是的倍數 $ p $ ，那麼它不是的倍數 $ q $ （假設）；在這種情況下 $ \gcd(B, N) = p $

引用自：https://crypto.stackexchange.com/questions/87770