# ポラード・ロー素因数分解法 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($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 = 100;
	
	# 2の倍数を取り除く
	$GCD = &EUCLIDEANALGORITHM($A, $NaturalNumber);
	if((1 < $GCD) && ($GCD < $NaturalNumber)){
		# 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;
		# 最大公約数
		$GCD = &EUCLIDEANALGORITHM(($X - 1), $NaturalNumber);
	
		# 素因数があるなら
		last if((1 < $GCD) && ($GCD < $NaturalNumber));
	}
	
	# 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;
}