積の素因数分解
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/07/18 03:21 UTC 版)
詳細は「素因数分解」を参照 秘匿による安全性（英語版）は、RSA暗号には及ばない。重要なことは、整数の素因数への分解の様子を明確に知ることである。RSA Factoring Challenge（英語版）と呼ばれる、公開されたリストにある整数を選んで因数分解できたものを表彰するコンペが、2007年5月まで開かれた。 エラトステネスの篩は分解の方法を与える素数判定法であるが、しかし巨大な整数には時間が掛かり過ぎて適用できない. 現在では平方剰余に基づく別な方法がしばしば用いられる。少なくとも二つの完全平方数を代表元に含む平方剰余が零因子になり、その二つの平方数を求めることが目標となる。このような方法が二次篩法（英語版）および一般数体篩法（英語版）であり、後者は2007年時点で最速である。また、ポラードの ρ アルゴリズムは誕生日のパラドクスに用いられる。
※この「積の素因数分解」の解説は、「合同算術」の解説の一部です。
「積の素因数分解」を含む「合同算術」の記事については、「合同算術」の概要を参照ください。
ウィキペディア小見出し辞書の「積の素因数分解」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- 積の素因数分解のページへのリンク
