發布一個小子群的生成器會削弱 RSA 模數嗎？
設n=P⋅問 $ n = P\cdot Q $ 是兩個安全素數P=2個p+1個 $ P = 2p+1 $ 和問=2個q+1個 $ Q=2q+1 $ 的乘積。設G $ g $ 是Cp⊂Z＊n $ C_{p} \subset \mathbb{Z}_n^* $ p $ p $ 階的乘法子群。換句話說，Gp=1個(模組n) $ g^p = 1 \pmod n $ 。（但p $ p $ 當然仍然是秘密。）
如果G $ g $ 是公開的，它會削弱 RSA 模數嗎？q $ q $ 已知時，計算這樣的生成器很容易，否則似乎很難。
是的，因為Gp≡1個(模組n) $ g^p\equiv 1\pmod n $ 意味著Gp≡1個(模組問) $ g^p\equiv 1\pmod Q $ 。通過費馬小定理，我們還知道G2個q≡1個(模組問) $ g^{2q}\equiv 1\pmod Q $ 和因此G一個p+b(2個q)≡1個(模組q) $ g^{ap+b(2q)}\equiv 1\pmod q $ 對於所有整數一個 $ a $ 和b $ b $ 。如果我們假設P $ P $ 和問 $ Q $ 是不同的（並且也避免了平凡的情況P=5個 $ P=5 $ ），那麼p $ p $ 和2個q $ 2q $ 是互質的，因此存在一個 $ a $ 和b $ b $ 使得一個p+b(2個q)=1個 $ ap+b(2q)=1 $ 並且因此G≡1個(模組問) $ g\equiv 1\pmod Q $ 。在這種情況下GC丁(G−1個,n)=問 $ \mathrm{GCD}(g-1,n)=Q $ 。
如果P=問 $ P=Q $ 那麼n $ n $ 是一個完美的平方並且可以快速分解。同樣，如果P=5個 $ P=5 $ 試驗劃分就足夠了。