リチャード・ブレントによる変形
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2018/08/22 13:42 UTC 版)
「ポラード・ロー素因数分解法」の記事における「リチャード・ブレントによる変形」の解説
1980年、リチャード・ブレントはこのアルゴリズムを変形して高速化したものを発表した。彼はポラードと同じ考え方を基本としたが、フロイドの循環検出法よりも高速に循環を検出する方法を使った。そのアルゴリズムは以下の通りである。 入力: n、素因数分解対象の整数; x0、ここで 0 ≤ x0 ≤ n; m、ここで m > 0; f(x)、n を法とする擬似乱数発生関数 出力: nの自明でない素因数、または失敗 y ← x0, r ← 1, q ← 1. Do:x ← y For i = 1 To r:y ← f(y) k ← 0 Do:ys ← y For i = 1 To min(m, r − k):y ← f(y) q ← (q × |x − y|) mod n g ← GCD(q, n) k ← k + m Until (k ≥ r or g > 1) r ← 2r Until g > 1 If g = n thenDo:ys ← f(ys) g ← GCD(|x − ys|, n) Until g > 1 If g = n then return failure, else return g
※この「リチャード・ブレントによる変形」の解説は、「ポラード・ロー素因数分解法」の解説の一部です。
「リチャード・ブレントによる変形」を含む「ポラード・ロー素因数分解法」の記事については、「ポラード・ロー素因数分解法」の概要を参照ください。
ウィキペディア小見出し辞書の「リチャード・ブレントによる変形」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- リチャード・ブレントによる変形のページへのリンク
