素因数分解とは サイエンスの人気・最新記事を集めました - はてな (original) (raw)

素因数分解

(

サイエンス

)

【

そいんすうぶんかい

】

整数Nを素数の積としてあらわすこと。
アルゴリズムとしては以下のものが知られている。

公開鍵暗号の一部*1では二つの巨大な素数の積が鍵として用いられる。これをもとの素数に分解すれば暗号を破れるが、莫大な計算を必要とするので事実上不可能であることがセキュリティのかなめとなっている。また、量子コンピュータが実現すれば、Shorのアルゴリズムにより確率的多項式時間で解けることが分かっている。

関連用語

*リスト：リスト::数学関連

*1:具体的にはRSA暗号、Rabin暗号、Goldwasser-Micali暗号等

このタグの解説についてこの解説文は、すでに終了したサービス「はてなキーワード」内で有志のユーザーが作成・編集した内容に基づいています。その正確性や網羅性をはてなが保証するものではありません。問題のある記述を発見した場合には、お問い合わせフォームよりご連絡ください。