Multiplicative order: Difference between revisions
Rename Perl 6 -> Raku, alphabetize, minor clean-up
(Add Factor) |
Thundergnat (talk | contribs) (Rename Perl 6 -> Raku, alphabetize, minor clean-up) |
||
Line 374:
}</lang>
=={{header|C
{{trans|Java}}
<lang csharp>using System;
Line 717 ⟶ 572:
ord(1511678068) mod 7379191741 = 614932645
ord(3047753288) mod 2257683301 = 62713425</pre>
=={{header|C++}}==
{{trans|C}}
<lang cpp>#include <algorithm>
#include <bitset>
#include <iostream>
#include <vector>
typedef unsigned long ulong;
std::vector<ulong> primes;
typedef struct {
ulong p, e;
} prime_factor; /* prime, exponent */
void sieve() {
/* 65536 = 2^16, so we can factor all 32 bit ints */
constexpr int SIZE = 1 << 16;
std::bitset<SIZE> bits;
bits.flip(); // set all bits
bits.reset(0);
bits.reset(1);
for (int i = 0; i < 256; i++) {
if (bits.test(i)) {
for (int j = i * i; j < SIZE; j += i) {
bits.reset(j);
}
}
}
/* collect primes into a list. slightly faster this way if dealing with large numbers */
for (int i = 0; i < SIZE; i++) {
if (bits.test(i)) {
primes.push_back(i);
}
}
}
auto get_prime_factors(ulong n) {
std::vector<prime_factor> lst;
ulong e, p;
for (ulong i = 0; i < primes.size(); i++) {
p = primes[i];
if (p * p > n) break;
for (e = 0; !(n % p); n /= p, e++);
if (e) {
lst.push_back({ p, e });
}
}
if (n != 1) {
lst.push_back({ n, 1 });
}
return lst;
}
auto get_factors(ulong n) {
auto f = get_prime_factors(n);
std::vector<ulong> lst{ 1 };
size_t len2 = 1;
/* L = (1); L = (L, L * p**(1 .. e)) forall((p, e)) */
for (size_t i = 0; i < f.size(); i++, len2 = lst.size()) {
for (ulong j = 0, p = f[i].p; j < f[i].e; j++, p *= f[i].p) {
for (size_t k = 0; k < len2; k++) {
lst.push_back(lst[k] * p);
}
}
}
std::sort(lst.begin(), lst.end());
return lst;
}
ulong mpow(ulong a, ulong p, ulong m) {
ulong r = 1;
while (p) {
if (p & 1) {
r = r * a % m;
}
a = a * a % m;
p >>= 1;
}
return r;
}
ulong ipow(ulong a, ulong p) {
ulong r = 1;
while (p) {
if (p & 1) r *= a;
a *= a;
p >>= 1;
}
return r;
}
ulong gcd(ulong m, ulong n) {
ulong t;
while (m) {
t = m;
m = n % m;
n = t;
}
return n;
}
ulong lcm(ulong m, ulong n) {
ulong g = gcd(m, n);
return m / g * n;
}
ulong multi_order_p(ulong a, ulong p, ulong e) {
ulong m = ipow(p, e);
ulong t = m / p * (p - 1);
auto fac = get_factors(t);
for (size_t i = 0; i < fac.size(); i++) {
if (mpow(a, fac[i], m) == 1) {
return fac[i];
}
}
return 0;
}
ulong multi_order(ulong a, ulong m) {
auto pf = get_prime_factors(m);
ulong res = 1;
for (size_t i = 0; i < pf.size(); i++) {
res = lcm(res, multi_order_p(a, pf[i].p, pf[i].e));
}
return res;
}
int main() {
sieve();
printf("%lu\n", multi_order(37, 1000)); // expect 100
printf("%lu\n", multi_order(54, 100001)); // expect 9090
return 0;
}</lang>
{{out}}
<pre>100
9090</pre>
=={{header|Clojure}}==
Translation of Julie, then revised to be more clojure idiomatic. It references some external modules for factoring and integer exponentiation.
<lang clojure>(defn gcd [a b]
(if (zero? b)
a
(recur b (mod a b))))
(defn lcm [a b]
(/ (* a b) (gcd a b)))
(def NaN (Math/log -1))
(defn ord' [a [p e]]
(let [m (imath/expt p e)
t (* (quot m p) (dec p))]
(loop [dv (factor/divisors t)]
(let [d (first dv)]
(if (= (mmath/expm a d m) 1)
d
(recur (next dv)))))))
(defn ord [a n]
(if (not= (gcd a n) 1)
NaN
(->>
(factor/factorize n)
(map (partial ord' a))
(reduce lcm))))
</lang>
{{out}}
<pre>
user=> (ord 37 1000)
100
</pre>
=={{header|D}}==
Line 919 ⟶ 954:
→ 15485862
</lang>
=={{header|Factor}}==
Line 1,488:
say znorder(Mod(54, 100001));
say znorder(Mod(11, 1 + Math::Pari::PARI(10)**100));</lang>
=={{header|Phix}}==
Line 1,797 ⟶ 1,735:
109609547199756140150989321269669269476675495992554276140800
</lang>
=={{header|Raku}}==
(formerly Perl 6)
<lang perl6>my @primes := 2, |grep *.is-prime, (3,5,7...*);
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 factor($t) -> $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 || die "$a and $m are not relatively prime";
[lcm] flat 1, factor($m).map(-> $r { mo-prime($a, $r.key, $r.value) });
}
sub MAIN("test") {
use Test;
for (10, 21, 25, 150, 1231, 123141, 34131) -> $n {
is ([*] factor($n).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';
}</lang>
{{out}}
<pre>ok 1 - 10 factors correctly
ok 2 - 21 factors correctly
ok 3 - 25 factors correctly
ok 4 - 150 factors correctly
ok 5 - 1231 factors correctly
ok 6 - 123141 factors correctly
ok 7 - 34131 factors correctly
ok 8 - mo(37,1000) == 100
ok 9 - mo(2,10**20-1) == 3748806900
ok 10 - mo(17,10**20-1) == 1499522760
ok 11 - mo(54,100001) == 9090</pre>
=={{header|REXX}}==
| |||