数論アルゴリズム

𝜌法
7.6 川原未鈴
目次
 𝜌法とは
 𝜌法の手順
 改良版𝜌法の手順
 𝜌法の良い点、課題点
5.2.2 𝜌法
非常に大きい奇数が合成数であることがわかっている
とする。
≪素数判定法≫
試行割算（最も遅い方法）・・・𝑛が合成数＋素因子
が判る
より高速な素数判定アルゴリズム・・・ 𝑛が合成数
𝑛より小さい素数による試行割算は 𝑛 以上のビット
𝜌 ロー
演算を必要とする。この方法よりも実質的に速く、最
も単純なアルゴリズムは J.M.Pollard 法
が開発した
（別名“モンテカルロ法”）である。
𝜌法の手順
Step１ ℤ/𝑛ℤから自分自身への計算が容易でℤ/𝑛ℤ全体に一
様
に分布するであろうと思われている写像、即ち、
𝑓 𝑥 = 𝑥2 + 𝑐
(𝑐 ∈ 1, 𝑛 − 3 )のような
整数係数の非常に単純な多項式を選択する。
Step２ある特定の値 𝑥 = 𝑥0 (𝑥0 ∈ 0, 𝑛 − 1 )を選択し、
𝑥1 = 𝑓(𝑥0 ),𝑥2 = 𝑓(𝑓(𝑥0 )),𝑥3 = 𝑓(𝑓(𝑓(𝑥0 ))),⋯
と次々に繰り返し写像の値を計算する。即ち、
𝑥𝑗+1 = 𝑓(𝑥𝑗 ), j=０,１,２と定義する。
Step３
な
𝑥𝑗 ≢ 𝑥𝑘 (mod 𝑛), 𝑑 ∣ 𝑛, 𝑥𝑗 ≡ 𝑥𝑘 (mod 𝑑), となるよう
𝑥𝑗 , 𝑥𝑘 があれば、 𝑑 ∣gcd(𝑥𝑗 −𝑥𝑘 , 𝑛) となり、
gcd(𝑥𝑗 −𝑥𝑘 , 𝑛)が𝑛 の真の因数となる。
例１
𝑓 𝑥 = 𝑥 2 + 1 , 𝑥0 = 1 を用いて９１を素因数分解する。
Step１
Step２
Step３
𝑓 𝑥 = 𝑥2 + 1
𝑥0 = 1,
𝑥1 = 𝑓(𝑥0 ) = 12 + 1 = 2,
𝑥2 = 𝑓(𝑥1 ) = 22 + 1 = 5,
𝑥3 = 𝑓(𝑥2 ) = 52 + 1 = 26,
gcd(𝑥3 − 𝑥2 , 𝑛) = gcd(21,91) = 7
よって、９１の因子は７
手順確認
𝜌法の手順（改良版）
Step１ ℤ/𝑛ℤから自分自身への計算が容易でℤ/𝑛ℤ全体に一
様
に分布するであろうと思われている写像、即ち、
𝑓 𝑥 = 𝑥2 + 𝑐
(c ∈ 1, 𝑛 − 3 )のような
整数係数の非常に単純な多項式を選択する。
Step２ある特定の値 𝑥 = 𝑥0 (𝑥0 ∈ 0, 𝑛 − 1 )を選択し、
𝑥1 = 𝑓(𝑥0 ),𝑥2 = 𝑓(𝑓(𝑥0 )),𝑥3 = 𝑓(𝑓(𝑓(𝑥0 ))),⋯
と次々に繰り返し写像の値を計算する。即ち、
𝑥𝑗+1 = 𝑓(𝑥𝑗 ), j=０,１,２と定義する。
Step３
うな
𝑥𝑗 ≢ 𝑥2𝑗 (mod 𝑛), 𝑑 ∣ 𝑛, 𝑥𝑗 ≡ 𝑥2𝑗 (mod 𝑑), となるよ
𝑥 , 𝑥 があれば、 𝑑 ∣ gcd(𝑥 −𝑥 , 𝑛) < 𝑛となり、
def IF_rho ( n, h = 100, i = 100 ) :
if n < 2 :
←ｎが小さすぎ
raise ValueError, "IF_rho ( n, h = 100, i = 100 ) n > 1 ?"
if h < 1 or i < 1 : # no trial error
raise ValueError, "IF_rho ( n, h = 100, i = 100 ) h, i > 0 ?"
def f ( s ) :
return ( s * s + c ) % n
for j in range ( h ) :
b=c=n-2
while c == b :
c = random.randrange ( 1, n )
for k in range ( i ) :
t = random.randrange ( n )
d = gcd.gcd ( t, n )
if 1 < d < n :
return d
r=f(t)
d = gcd.gcd ( t - r, n )
while d == 1 :
t, r = f ( t ), f ( f ( r ) )
d = gcd.gcd ( t - r, n )
if d < n :
return d
print “Failed to find IF” return None
𝑓 𝑠 を決め
る
ｃを選ぶ
f ( s ) ＝ s * s －２はダメ
初期値を選ぶ（カメ）
因数見つけた
←ウサギ
因数見つけた
※「因数が見つからなかった＝𝑛は素数」という訳
良い点
課題点
 𝑓 𝑥 が果たしてℤ/𝑛でランダ
 計算量が指数時間
1
4
1
4
𝑂（𝑛 lg 𝑛）=Õ(𝑛 )
で試行割算より少ない
ムに分布する数列を生成す
るかどうか
 𝑐と初期値の値をどの範囲で
 実際に計算する数列の項数
は 4 𝑛の数倍程度で、必要記
憶容量が数個で済む
選ぶかによって、因数が見
つかったり、見つからな
かったりする。

Download Report