Prime-Numbers
是否容易分解多個形式n=噸2⋅pn=噸2⋅pn = t^{2} cdotp p?
是否容易分解多個形式 $ n = t^{2} \cdotp p $ ， 在哪裡 $ t $ 和 $ p $ 是大素數嗎？
形式的整數 $ n = p\cdot q^2 $ , $ p $ 和 $ q $ 素數是一些公鑰密碼系統的基礎，包括ESIGN、Okamoto-Uchiyama密碼系統，這些密碼系統基於找到二次域的類數的難度。因此，能夠有效地分解這種形式的數字將立即破壞許多密碼系統。這將是一件大事。此外，這也與數論中的一個經典問題有關，這將是一個獨立的興趣。
至於針對此類整數的具體分解算法，有多種類型：
- Peralta 和 Okamoto針對這種形式稍微優化了 ECM，但結果並不明顯優於正常 ECM。
- Boneh、Durfee 和 Howgrave-Graham使用 Coppersmith 式的尋根技術來分解 $ n $ 大約在 $ n^{1/9} $ 操作時 $ p $ 和 $ q $ 大小相似。雖然這聽起來可能令人印象深刻，但對於密碼相關大小的數字來說，它並不比數字域篩更好。
- Castagnos、Joux、Laguillaumie 和 Nguyen觀察到，考慮到一些關於 $ n $ 可以考慮因素 $ n $ 在多項式時間內。但這不是一般情況，僅適用於特殊情況，例如NICE。