FC2ブログ

# リチャード・ブレント素因数分解法 Brent's Factorization Method
# 引数 自然数 ($NaturalNumber)
# 戻り値 リチャード・ブレント素因数分解法 (@PrimeFactorization)
sub BRENTSFACTORIZATIONMETHOD{
my ($NaturalNumber) = @_;
my @PrimeFactorization = ();
my $Brent = 1;
my $Constant = 1;
my $Position = 0;
$NaturalNumber = int($NaturalNumber);

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

while($Brent != 0){
# リチャード・ブレントによる変形
$Brent = &BRENT($NaturalNumber, $Constant);

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

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

return @PrimeFactorization;
}

# リチャード・ブレントによる変形
# 引数 自然数 ($NaturalNumber, $Constant);
# 戻り値 リチャード・ブレントによる変形 ($Brent)
sub BRENT{
my ($NaturalNumber, $Constant) = @_;
my $Brent = 0;
my $X = 2;
my $Y = 2;
my $GCD = 1;
my $Power = 1;
my $Count = 1;

# 計算
while($GCD == 1){
if($Power == $Count){
$X = $Y;
# 累乗
$Power = $Power * 2;
# 初期化
$Count = 0;
}

# 擬似乱数発生関数
$Y = &FUNCTION($Y, $Constant) % $NaturalNumber;
$Count++;

# 最大公約数
$GCD = &EUCLIDEANALGORITHM(abs($X - $Y), $NaturalNumber);
}

# リチャード・ブレントによる変形
$Brent = $GCD;

return $Brent;
}

# ユークリッドの互除法 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
12章 素因数分解アルゴリズム
ポラード・ロー素因数分解法 - Wikipedia
Cycle detection - Wikipedia, the free encyclopedia
素因数分解 - 高精度計算サイト

一言
これでいいのか?
オンライン コンパイラ/インタプリタ
テクニカル分析
プロフィール

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

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

検索フォーム


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