FC2ブログ
最初
http://blog-imgs-36.fc2.com/a/m/a/amamiyaprog/P-1Method1.txt

修正1 6/19

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

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

$NaturalNumber = int($NaturalNumber);

while(($NaturalNumber > 1) && ($PMinus1Method != 1)){
# P-1法 P-1 Method
$PMinus1Method = &PMINUS1METHOD($NaturalNumber);

if($PMinus1Method != 1){
$NaturalNumber = $NaturalNumber / $PMinus1Method;

# 素因数分解 Prime Factorization
$PrimeFactorization[$Position] = $PMinus1Method;
# 配列の位置
$Position++;
}else {
# 素因数分解 Prime Factorization
$PrimeFactorization[$Position] = $NaturalNumber;
}
}

return @PrimeFactorization;
}

# P-1法 P-1 Method
# 引数 自然数 ($NaturalNumber);
# 戻り値 P-1法 ($PMinus1Method)
sub PMINUS1METHOD{
my ($NaturalNumber) = @_;
my $PMinus1Method = 0;
my $A = 2;
my $M = 1;
my $X = 0;
my $GCD = 0;
my $Limit = 1000;

# 2の倍数を取り除く
$GCD = &EUCLIDEANALGORITHM($A, $NaturalNumber);
if(1 != $GCD){
# P-1法 P-1 Method
$PMinus1Method = $GCD;

return $PMinus1Method;
}

# 計算
for(my $i = 2; $i < $Limit; $i++){
$M = $i; # $M = $M * $i;
# 値
$X = ($A ** $M) % $NaturalNumber;
# ($X - 1) == 0 になるから
next if($X == 1);
# 最大公約数
$GCD = &EUCLIDEANALGORITHM(($X - 1), $NaturalNumber);

# 素因数があるなら
last if(1 != $GCD);
}

# P-1法 P-1 Method
$PMinus1Method = $GCD;

return $PMinus1Method;
}

# ユークリッドの互除法 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;
}


参考URL
算術算法研究-素因数分解- p-1 法
12章 素因数分解アルゴリズム
Pollard's p ? 1 algorithm - Wikipedia, the free encyclopedia
Pollard's P-1 Method
素因数分解 - 高精度計算サイト

一言
$M = $M * $i にすると Illegal modulus zero になるので $M = $i にしておく
$Limitの値が小さいと素因数分解しきれないことがある

修正1
next if($X == 1) を追加
1以外なら最大公約数があるので
((1 < $GCD) && ($GCD < $NaturalNumber))

(1 != $GCD
に二変更する
オンライン コンパイラ/インタプリタ
テクニカル分析
プロフィール

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

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

検索フォーム


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