構造具有特定totient的整數而不進行因式分解
給定 $ N(=pq) $ ，但不是它的因式分解。不知怎的，你設法知道， $ k $ 劃分 $ \phi(N) $ . 有沒有可能想出一個整數 $ N^{} $ , 為此 $ \phi(N^{})=\phi(N)/k $ , 沒有因式 $ N $ ?
評論： $ p $ 和 $ q $ 是不同的奇數素數（如果不是，我們可以因式分解 $ N $ ）， 因此 $ \phi(N)=(p-1)(q-1) $ . 定義 $ p’=(p-1)/2 $ 和 $ q’=(q-1)/2 $ . 它擁有 $ \phi(N)=4,p’,q’ $ .
所問的並不總是可能的。作為反例，假設 $ k=2 $ （這是一個可能的 $ k $ ，從上面的評論），和 $ p\equiv 3\equiv q\pmod4 $ （涵蓋了大約 25% 的 RSA 密鑰）。如果我們能找到 $ N^* $ 和 $ \phi(N^{})=\phi(N)/k $ ，它會成立 $ \phi(N^)=2,p’,q’ $ 和 $ p’ $ 和 $ q’ $ 奇怪的。因此¹ $ N^* $ 將是形式 $ 2^s,r^t $ 和 $ r $ 素數，與 $ \phi(N^)=(r-1),r^{t-1} $ . 因此我們可以考慮 $ N^ $ , 產生 $ r $ 和 $ e $ ， 因此 $ \phi(N^*) $ ， 因此 $ \phi(N) $ , 允許因式 $ N $ .
仍然與 $ k=2 $ , $ p\equiv3\pmod4 $ , 但這次 $ q\equiv5\pmod8 $ （涵蓋另外大約 25% 的 RSA 密鑰），我們有 $ \phi(N^*)=4,p’,q’’ $ 和 $ p’ $ 和 $ q’’=(q-1)/4 $ 奇數，兩個可能的（非排他的）選項是²
- 那 $ N^* $ 是形式 $ 2^s,r^e $ 和 $ r $ 素數，我們如上所述處理。
- 那 $ N^=(2,p’+1),(2,q’’+1) $ 和 $ (2,p’+1) $ 和 $ (2,q’’+1) $ 不同的素數，在這種情況下 $ N^=p,((q+1)/2) $ ， 因此 $ \gcd(N,N^*) $ 將會 $ p $ , 產生一個因式分解 $ N $ .
更一般地說，如果所問的問題是可能的，那麼至少有以下一項可能成立：
- $ \gcd(N,N^*) $ 揭示了一個因素 $ N $ .
- 我們可以考慮 $ N^* $ （包括但不僅限於 $ N^=2^s,r^t $ )，然後可以計算 $ \phi(N^) $ ， 因此 $ \phi(N) $ , 允許我們考慮 $ N $ .
我有一種隨機的機會 $ N $ 什麼時候 $ k $ 是小。
獨立：何時 $ k $ 很大，尤其是當它是素數時，它的價值是有啟發性的：它必須除 $ p-1 $ 或者 $ q-1 $ ， 因此 $ \gcd(N,j,k+1) $ 將會 $ p $ 或者 $ q $ 對於一些 $ j $ , 值得嘗試尋找 $ j $ 通過列舉至少當 $ \sqrt N/k $ 足夠小，沒有理由相信 $ \max(p,q)/\min(p,q) $ 很大。
什麼時候 $ k $ 有一個很大的素因數 $ k’ $ 我們可以找到 $ k’ $ 必須分開 $ p-1 $ 或者 $ q-1 $ ，我們也許可以使用相同的方法來分解 $ N $ . 幸運的是，該產品 $ k’,k’’ $ 在哪裡 $ k’’ $ 是一個很大的因素 $ k/k’ $ 會分 $ p-1 $ 或者 $ q-1 $ , 允許因式 $ N $ . 即使我們不能完全考慮 $ k $ ，因為我們發現的最大因子是複合的，它仍然有公平的機會去劃分 $ p-1 $ 或者 $ q-1 $ , 允許因式 $ N $ .
我隱約猜想（不會打賭）半素數很少 $ N $ 這樣一個知道其因式分解的預言機就可以揭示 $ k $ , $ N^* $ 正如在問題中沒有上述技術的組合對因素有很大幫助 $ N $ . 換句話說，對於絕大多數人來說，所要求的顯然是不可能的 $ N $ .
¹ 這使用以下引理：如果 $ \phi(m)\equiv2\pmod4 $ ， 然後 $ m $ 是形式 $ 2^s,r^t $ 和 $ r $ 主要。該引理的證明可以通過使用 Euler 的 totient 表達式的對置：$$ \phi\left(\prod_{p_i\text{ distinct primes}} {p_i}^{e_i}\right)=\prod_{\text{same }(p_i,e_i)}(p_i-1),{p_i}^{(e_i-1)} $$
² 這留給讀者作為練習，使用與上述引理相同的論證。