Multiplicative order: Difference between revisions
Content added Content deleted
(Add Factor) |
Thundergnat (talk | contribs) (Rename Perl 6 -> Raku, alphabetize, minor clean-up) |
||
Line 374: | Line 374: | ||
}</lang> |
}</lang> |
||
=={{header|C |
=={{header|C sharp|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|C#|C sharp}}== |
|||
{{trans|Java}} |
{{trans|Java}} |
||
<lang csharp>using System; |
<lang csharp>using System; |
||
Line 717: | Line 572: | ||
ord(1511678068) mod 7379191741 = 614932645 |
ord(1511678068) mod 7379191741 = 614932645 |
||
ord(3047753288) mod 2257683301 = 62713425</pre> |
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}}== |
=={{header|D}}== |
||
Line 919: | Line 954: | ||
→ 15485862 |
→ 15485862 |
||
</lang> |
</lang> |
||
=={{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|Factor}}== |
=={{header|Factor}}== |
||
Line 1,488: | Line 1,488: | ||
say znorder(Mod(54, 100001)); |
say znorder(Mod(54, 100001)); |
||
say znorder(Mod(11, 1 + Math::Pari::PARI(10)**100));</lang> |
say znorder(Mod(11, 1 + Math::Pari::PARI(10)**100));</lang> |
||
=={{header|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|Phix}}== |
=={{header|Phix}}== |
||
Line 1,797: | Line 1,735: | ||
109609547199756140150989321269669269476675495992554276140800 |
109609547199756140150989321269669269476675495992554276140800 |
||
</lang> |
</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}}== |
=={{header|REXX}}== |