FC2ブログ

# ポラード・ロー素因数分解法 Pollard's Rho Algorithm
# 引数 自然数 ($NaturalNumber)
# 戻り値 ポラード・ロー素因数分解法 (@PrimeFactorization)
sub POLLARDSRHOALGORITHM{
my ($NaturalNumber) = @_;
my @PrimeFactorization = ();
my $PMethod = 1;
my $Constant = 1;
my $Position = 0;

# 自然数の確認
if($NaturalNumber < 1){
return 0;
}

$NaturalNumber = int($NaturalNumber);

while($PMethod != 0){
# P法 P Method
$PMethod = &PMETHOD($NaturalNumber, $Constant);

if($PMethod != 0){
$NaturalNumber = $NaturalNumber / $PMethod;

# 擬似乱数発生関数の定数部分を変更
$Constant = $PMethod;
# 素因数分解 Prime Factorization
$PrimeFactorization[$Position] = $PMethod;
# 配列の位置
$Position++;
}else {
# 素因数分解 Prime Factorization
$PrimeFactorization[$Position] = $NaturalNumber;
}
}

return @PrimeFactorization;
}

# P法 P Method
# 引数 自然数 ($NaturalNumber, $Constant);
# 戻り値 P法 ($PMethod)
sub PMETHOD{
my ($NaturalNumber, $Constant) = @_;
my $PMethod = 0;
my $X = 2;
my $Y = 2;
my $GCD = 1;

# 計算
while($GCD == 1){
# 擬似乱数発生関数
$X = &FUNCTION($X, $Constant) % $NaturalNumber;
$Y = &FUNCTION($Y, $Constant) % $NaturalNumber;
$Y = &FUNCTION($Y, $Constant) % $NaturalNumber;
# 最大公約数
$GCD = &EUCLIDEANALGORITHM(abs($X - $Y), $NaturalNumber);
}

# P法 P Method
$PMethod = $GCD;

return $PMethod;
}

# ユークリッドの互除法 Euclidean Algorithm
# 引数 自然数 自然数 ($a, $b)
# 戻り値 最大公約数 ($EuclideanAlgorithm)
sub EUCLIDEANALGORITHM{
my ($a, $b) = @_;
my $EuclideanAlgorithm = 0;
my $A = int(abs($a));
my $B = int(abs($b));
my $Remainder = 1;

# 値の確認
if(($A == 0) || ($B == 0)){
return 0;
}

($A, $B) = ($B, $A) if($A < $B);

# 計算
while($Remainder != 0){
# 余り
$Remainder = $A % $B;

$A = $B;
$B = $Remainder;
}

# ユークリッドの互除法 Euclidean Algorithm
$EuclideanAlgorithm = $A;

return $EuclideanAlgorithm;
}

# 擬似乱数発生関数 Function
# 引数 値 定数 ($X, $Constant)
# 戻り値 擬似乱数発生関数 ($Function)
sub FUNCTION{
my ($X, $Constant) = @_;
my $Function = ($X * $X) + $Constant;

return $Function;
}


参考URL
ポラード・ロー素因数分解法 - Wikipedia
12章 素因数分解アルゴリズム
算術算法研究-素因数分解-ρ法(モンテカルロ法)
素因数分解 - 高精度計算サイト

一言
素因数分解に2の倍数が残っていることがある
素因数分解しきれていないことがある
定数部分を変更するやり方は、これでよいのか?
オンライン コンパイラ/インタプリタ
テクニカル分析
プロフィール

Author:雨宮
Firefoxを使用しているので気づかなかったけど、IE6でソースコードを上手くコピーできない

5/3
携帯用ならIE6でもソースコードをコピーできる
携帯用

検索フォーム


あわせて読みたいブログパーツ
一寸先は闇 RSS