Rosetta Code

Multiplicative order: Difference between revisions

Page Discussion

Multiplicative order (view source)

Revision as of 19:02, 30 May 2021

346 bytes removed ,  3 years ago
m
→‎{{header|Raku}}: Modernize, speed up quite a bit (meh, goes from ~1/2 second to ~1/4 second)
m (→‎{{header|Raku}}: Modernize, speed up quite a bit (meh, goes from ~1/2 second to ~1/4 second))
Line 1,834:
=={{header|Raku}}==
(formerly Perl 6)
<lang perl6>my @primesuse Prime:= 2, |grep *.is-prime, (3,5,7...*):Factor;
 
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 mo-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 factorprime-factors($t).Bag -> $f {
@qs = flat @qs.map(-> $q { (0..$f.value).map(-> $j { $q * $f.key ** $j }) });
}
 
@qs.sort.first(: -> $q { expmod( $a, $q, $m ) == 1 });
}
 
sub mo($a, $m) {
$a gcd $m == 1 ||or die "$a and $m are not relatively prime";
[lcm] flat 1, factorprime-factors($m).Bag.map(-> $r: { mo-prime($a, $r.key, $r.value) });
}
 
submulti MAIN("'test"') {
use Test;
 
for (10, 21, 25, 150, 1231, 123141, 34131) -> $n {
is ([*] factorprime-factors($n).Bag.map(-> $pair { $pair.key ** $pair.value } )), $n, "$n factors correctly";
}
 
is mo(37, 1000), 100, 'mo(37,1000) == 100';
my $b = 10**20-1;
is mo(2, $b), 3748806900, 'mo(2,10**20-1) == 3748806900';
is mo(17, $b), 1499522760, 'mo(17,10**20-1) == 1499522760';
$b = 100001;
is mo(54, $b), 9090, 'mo(54,100001) == 9090';
Thundergnat
10,333

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/48339"