Skip to content
Permalink
Branch: master
Find file Copy path
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
36 lines (33 sloc) 1.07 KB
use v6;
unit module Prime::Factor:ver<0.2.4>:auth<github:thundergnat>;
sub prime-factors ( Int $n where * > 0 ) is export {
return $n if $n.is-prime;
return [] if $n == 1;
my $factor = find-factor( $n );
sort flat prime-factors( $factor ), prime-factors( $n div $factor );
}
# use Pollard's rho algorithm to speed factorization
# See Wikipedia "Pollard's rho algorithm" and
# Damian Conways "On the Shoulders of Giants" presentation from YAPC::NA 2016
sub find-factor ( Int $n, $constant = 1 ) {
return 2 unless $n +& 1;
if (my $gcd = $n gcd 6541380665835015) > 1 { # magic number: [*] primes 3 .. 43
return $gcd if $gcd != $n
}
my $x = 2;
my $rho = 1;
my $factor = 1;
while $factor == 1 {
$rho = $rho +< 1;
my $fixed = $x;
my int $i = 0;
while $i < $rho {
$x = ( $x * $x + $constant ) % $n;
$factor = ( $x - $fixed ) gcd $n;
last if 1 < $factor;
$i = $i + 1;
}
}
$factor = find-factor( $n, $constant + 1 ) if $n == $factor;
$factor;
}
You can’t perform that action at this time.