gistfile1.txt

my @primes := (2..*).grep(*.is-prime);

sub factor($a is copy) {
    gather {
        for @primes -> $p {
            my $j = 0;
            while $a %% $p {
                $a div= $p;
                $j++;
            }
            take $p => $j if $j > 0;
            last if $a < $p * $p;
        }
        
        take $a => 1 if $a > 1;
    }
}
 
sub multiplicative-order-prime($a, $p, $e) {
    my $m = $p ** $e;
    my $t = ($p - 1) * ($p ** ($e - 1)); #  = Phi($p**$e) where $p prime
    my @qs = 1;
    for factor($t) -> $f {
        @qs = @qs.map(-> $q { (0..$f.value).map(-> $j { $q * $f.key ** $j }) });
    }
    @qs.sort();
 
    @qs.first(-> $q { expmod( $a, $q, $m ) == 1});
}
 
sub multiplicative-order($a, $m) {
    $a gcd $m == 1 || die "$a and $m are not relatively prime";
    [lcm] 1, factor($m).map(-> $r { multiplicative-order-prime($a, $r.key, $r.value) });
}
 
sub MAIN("test") {
    use Test;
    
    for (10, 21, 25, 150, 1231, 123141, 34131) -> $n {
        # say factor($n).perl;
        # say factor($n).map(-> $pair { $pair.key ** $pair.value }).perl;
        is ([*] factor($n).map(-> $pair { $pair.key ** $pair.value })), $n, "$n factors correctly";
    }
    
    is multiplicative-order(37, 1000), 100;
    my $b = 10**20-1;
    is multiplicative-order(2, $b), 3748806900;
    is multiplicative-order(17, $b), 1499522760;
    $b = 100001;
    # is multOrder(54, $b), 
    # #     print pow( 54, multOrder(54,b),b)
    
    # say multOrder(37, 1000);
}