Multiplicative order: Difference between revisions

m
syntax highlighting fixup automation
(Added 11l)
m (syntax highlighting fixup automation)
Line 49:
{{trans|D}}
 
<langsyntaxhighlight lang="11l">T PExp
BigInt prime
Int exp
Line 125:
 
moTest(1511678068, 7379191741)
moTest(BigInt(‘3047753288’), BigInt(‘2257683301’))</langsyntaxhighlight>
 
{{out}}
Line 139:
=={{header|Ada}}==
Instead of assuming a library call to factorize the modulus, we assume the caller of our Find_Order function has already factorized it. The Multiplicative_Order package is specified as follows ("multiplicative_order.ads").
<langsyntaxhighlight Adalang="ada">package Multiplicative_Order is
 
type Positive_Array is array (Positive range <>) of Positive;
Line 159:
-- (2) 1 < Coprime_Factors(I) for all I
 
end Multiplicative_Order;</langsyntaxhighlight>
 
Here is the implementation ("multiplicative_order.adb"):
 
<langsyntaxhighlight Adalang="ada">package body Multiplicative_Order is
 
function Find_Order(Element, Modulus: Positive) return Positive is
Line 228:
end Find_Order;
 
end Multiplicative_Order;</langsyntaxhighlight>
 
This is a sample program using the Multiplicative_Order package:
<langsyntaxhighlight Adalang="ada">with Ada.Text_IO, Multiplicative_Order;
 
procedure Main is
Line 254:
-- it gives an incorrect result
IIO.Put(Find_Order(37, (11, 19, 8, 2)));
end Main;</langsyntaxhighlight>
 
The output from the sample program:
Line 269:
{{works with|ALGOL 68G|Any - tested with release mk15-0.8b.fc9.i386}}
<!-- {{does not work with|ELLA ALGOL 68|Any (with appropriate job cards AND formatted transput statements removed) - tested with release 1.8.8d.fc9.i386 - ELLA has no FORMATted transput, also it generates a call to undefined C LONG externals }} -->
<langsyntaxhighlight lang="algol68">MODE LOOPINT = INT;
 
MODE POWMODSTRUCT = LONG INT;
Line 388:
printf(($g$, "Everything checks.", $l$))
FI
)</langsyntaxhighlight>
Output:
<pre>
Line 401:
=={{header|C}}==
Uses prime/factor functions from [[Factors of an integer#Prime factoring]]. This implementation is not robust because of integer overflows. To properly deal with even moderately large numbers, an arbitrary precision integer package is a must.
<langsyntaxhighlight lang="c">ulong mpow(ulong a, ulong p, ulong m)
{
ulong r = 1;
Line 463:
printf("%lu\n", multi_order(54, 100001));
return 0;
}</langsyntaxhighlight>
 
=={{header|C sharp|C#}}==
{{trans|Java}}
<langsyntaxhighlight lang="csharp">using System;
using System.Collections.Generic;
using System.Numerics;
Line 655:
}
}
}</langsyntaxhighlight>
{{out}}
<pre>ord(37) mod 3343 = 1114
Line 666:
=={{header|C++}}==
{{trans|C}}
<langsyntaxhighlight lang="cpp">#include <algorithm>
#include <bitset>
#include <iostream>
Line 804:
 
return 0;
}</langsyntaxhighlight>
{{out}}
<pre>100
Line 811:
=={{header|Clojure}}==
Translation of Julie, then revised to be more clojure idiomatic. It references some external modules for factoring and integer exponentiation.
<langsyntaxhighlight lang="clojure">(defn gcd [a b]
(if (zero? b)
a
Line 837:
(map (partial ord' a))
(reduce lcm))))
</syntaxhighlight>
</lang>
{{out}}
<pre>
Line 846:
=={{header|D}}==
{{trans|Java}}
<langsyntaxhighlight lang="d">import std.bigint;
import std.random;
import std.stdio;
Line 1,001:
moTest(1511678068, 7379191741);
moTest(3047753288, 2257683301);
}</langsyntaxhighlight>
{{out}}
<pre>ord(37) mod 3343 = 1114
Line 1,011:
 
=={{header|EchoLisp}}==
<langsyntaxhighlight lang="scheme">
(require 'bigint)
 
Line 1,044:
(order (+ (expt 10 1000) 1) 15485863)
→ 15485862
</syntaxhighlight>
</lang>
 
=={{header|Factor}}==
{{works with|Factor|0.99 2020-01-23}}
<langsyntaxhighlight lang="factor">USING: kernel math math.functions math.primes.factors sequences ;
 
: (ord) ( a pair -- n )
Line 1,058:
2dup gcd nip 1 =
[ group-factors [ (ord) ] with [ lcm ] map-reduce ]
[ 2drop 0/0. ] if ;</langsyntaxhighlight>
{{out}}
<pre>
Line 1,068:
 
=={{header|Go}}==
<langsyntaxhighlight lang="go">package main
 
import (
Line 1,169:
}
return a.SetInt64(0)
}</langsyntaxhighlight>
{{out}}
<pre>
Line 1,184:
Assuming a function
 
<langsyntaxhighlight lang="haskell">powerMod
:: (Integral a, Integral b)
=> a -> a -> b -> a
Line 1,198:
| even i = g (b * b `rem` m) (i `quot` 2)
| otherwise = f b (i - 1) (b * y `rem` m)
powerMod m _ _ = error "powerMod: negative exponent"</langsyntaxhighlight>
 
to efficiently calculate powers modulo some <code>Integral</code>, we get
 
<langsyntaxhighlight lang="haskell">import Data.List (foldl1') --'
 
foldl1_ = foldl1' --'
Line 1,218:
where
x = powerMod pk a (t `div` (q ^ e))
d = length $ takeWhile (/= 1) $ iterate (\y -> powerMod pk y q) x</langsyntaxhighlight>
 
=={{header|J}}==
Line 1,224:
The dyadic verb ''mo'' converts its arguments to exact numbers ''a'' and ''m'', executes ''mopk'' on the factorization of ''m'', and combines the result with the ''least common multiple'' operation.
 
<langsyntaxhighlight lang="j">mo=: 4 : 0
a=. x: x
m=. x: y
assert. 1=a+.m
*./ a mopk"1 |: __ q: m
)</langsyntaxhighlight>
 
The dyadic verb ''mopk'' expects a pair of prime and exponent
Line 1,238:
exponents ''q^d'' into a product.
 
<langsyntaxhighlight lang="j">mopk=: 4 : 0
a=. x: x
'p k'=. x: y
Line 1,247:
d=. (1<x)+x (pm i. 1:)&> (e-1) */\@$&.> q
*/q^d
)</langsyntaxhighlight>
 
For example:
 
<langsyntaxhighlight lang="j"> 37 mo 1000
100
2 mo _1+10^80x
190174169488577769580266953193403101748804183400400</langsyntaxhighlight>
 
=={{header|Java}}==
{{trans|Kotlin}}
<langsyntaxhighlight Javalang="java">import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;
Line 1,363:
moTest(BigInteger.valueOf(3047753288L), BigInteger.valueOf(2257683301L));
}
}</langsyntaxhighlight>
{{out}}
<pre>ord(37) mod 3343 = 1114
Line 1,374:
=={{header|Julia}}==
(Uses the <code>factors</code> function from [[Factors of an integer#Julia]].)
<langsyntaxhighlight lang="julia">using Primes
 
function factors(n)
Line 1,398:
end
res
end</langsyntaxhighlight>
 
Example output (using <code>big</code> to employ arbitrary-precision arithmetic where needed):
Line 1,417:
=={{header|Kotlin}}==
{{trans|Go}}
<langsyntaxhighlight lang="scala">// version 1.2.10
 
import java.math.BigInteger
Line 1,510:
moTest(BigInteger("1511678068"), BigInteger("7379191741"))
moTest(BigInteger("3047753288"), BigInteger("2257683301"))
}</langsyntaxhighlight>
 
{{out}}
Line 1,523:
 
=={{header|Maple}}==
<langsyntaxhighlight Maplelang="maple">numtheory:-order( a, n )</langsyntaxhighlight>
For example,
<langsyntaxhighlight Maplelang="maple">> numtheory:-order( 37, 1000 );
100</langsyntaxhighlight>
 
=={{header|Mathematica}}/{{header|Wolfram Language}}==
Line 1,533:
MultiplicativeOrder[k,n,{r1,r2,...}] gives the generalized multiplicative order of k modulo n, defined as the smallest integer m such that k^m==ri mod n for some i.<BR>
Examples:
<langsyntaxhighlight Mathematicalang="mathematica">MultiplicativeOrder[37, 1000]
MultiplicativeOrder[10^100 + 1, 7919] (*10^3th prime number Prime[1000]*)
MultiplicativeOrder[10^1000 + 1, 15485863] (*10^6th prime number*)
MultiplicativeOrder[10^10000 - 1, 22801763489] (*10^9th prime number*)
MultiplicativeOrder[13, 1 + 10^80]
MultiplicativeOrder[11, 1 + 10^100]</langsyntaxhighlight>
gives back:
<pre>100
Line 1,548:
 
=={{header|Maxima}}==
<langsyntaxhighlight lang="maxima">zn_order(37, 1000);
/* 100 */
 
Line 1,564:
 
zn_order(11, 1 + 10^100);
/* 2583496112724752500580158969425549088007844580826869433740066152289289764829816356800 */</langsyntaxhighlight>
 
=={{header|Nim}}==
{{trans|Kotlin}}
{{libheader|bignum}}
<langsyntaxhighlight Nimlang="nim">import strformat
import bignum
 
Line 1,652:
moTest(newInt("1511678068"), newInt("7379191741"))
 
moTest(newInt("3047753288"), newInt("2257683301"))</langsyntaxhighlight>
 
{{out}}
Line 1,663:
 
=={{header|PARI/GP}}==
<syntaxhighlight lang ="parigp">znorder(Mod(a,n))</langsyntaxhighlight>
 
=={{header|Perl}}==
Using modules:
{{libheader|ntheory}}
<langsyntaxhighlight lang="perl">use ntheory qw/znorder/;
say znorder(54, 100001);
use bigint; say znorder(11, 1 + 10**100);</langsyntaxhighlight>
or
<langsyntaxhighlight lang="perl">use Math::Pari qw/znorder Mod/;
say znorder(Mod(54, 100001));
say znorder(Mod(11, 1 + Math::Pari::PARI(10)**100));</langsyntaxhighlight>
 
=={{header|Phix}}==
{{trans|Ruby}}
{{libheader|Phix/mpfr}}
<!--<langsyntaxhighlight Phixlang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">include</span> <span style="color: #004080;">mpfr</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span>
Line 1,793:
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Everything checks. (%s)\n"</span><span style="color: #0000FF;">,{</span><span style="color: #7060A8;">elapsed</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t</span><span style="color: #0000FF;">)})</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<!--</langsyntaxhighlight>-->
{{out}}
<pre>
Line 1,817:
=={{header|Python}}==
 
<langsyntaxhighlight lang="python">def gcd(a, b):
while b != 0:
a, b = b, a % b
Line 1,882:
print 'Exists a power r < 9090 where pow(54,r,b)==1'
else:
print 'Everything checks.'</langsyntaxhighlight>
 
=={{header|Racket}}==
Line 1,889:
shown below.
 
<langsyntaxhighlight lang="racket">
#lang racket
(require math)
Line 1,915:
(order (- (expt 10 10000) 1) 22801763489)
(order 13 (+ 1 (expt 10 80)))
</syntaxhighlight>
</lang>
Output:
<langsyntaxhighlight lang="racket">
100
3959
Line 1,923:
22801763488
109609547199756140150989321269669269476675495992554276140800
</syntaxhighlight>
</lang>
 
=={{header|Raku}}==
(formerly Perl 6)
<syntaxhighlight lang="raku" perl6line>use Prime::Factor;
 
sub mo-prime($a, $p, $e) {
Line 1,958:
$b = 100001;
is mo(54, $b), 9090, 'mo(54,100001) == 9090';
}</langsyntaxhighlight>
{{out}}
<pre>ok 1 - 10 factors correctly
Line 1,973:
 
=={{header|REXX}}==
<langsyntaxhighlight lang="rexx">/*REXX pgm computes multiplicative order of a minimum integer N such that a^n mod m≡1*/
wa= 0; wm= 0 /* ═a═ ══m══ */ /*maximum widths of the A and M values.*/
@.=.; @.1= 3 10
Line 1,999:
say pad 'a=' right(a,wa) pad "m=" right(m,wm) pad 'multiplicative order:' n
end /*j*/
end /*w*/ /*stick a fork in it, we're all done. */</langsyntaxhighlight>
{{out|output|.}}
<pre>
Line 2,012:
=={{header|Ruby}}==
 
<langsyntaxhighlight lang="ruby">require 'prime'
 
def powerMod(b, p, m)
Line 2,052:
else
puts 'Everything checks.'
end</langsyntaxhighlight>
 
{{out}}
Line 2,065:
 
=={{header|Seed7}}==
<langsyntaxhighlight lang="seed7">$ include "seed7_05.s7i";
include "bigint.s7i";
 
Line 2,182:
moTest(1511678068_, 7379191741_);
moTest(3047753288_, 2257683301_);
end func;</langsyntaxhighlight>
 
{{out}}
Line 2,197:
 
Built-in:
<langsyntaxhighlight lang="ruby">say 37.znorder(1000) #=> 100
say 54.znorder(100001) #=> 9090</langsyntaxhighlight>
 
{{trans|Raku}}
<langsyntaxhighlight lang="ruby">func mo_prime(a, p, e) {
var m = p**e
var t = (p-1)*(p**(e-1))
Line 2,226:
say mo(2, b)
say mo(17, b)
}</langsyntaxhighlight>
{{out}}
<pre>
Line 2,238:
{{trans|Python}}
{{tcllib|struct::list}}
<langsyntaxhighlight lang="tcl">package require Tcl 8.5
package require struct::list
 
Line 2,415:
if {$r % 1000 == 0} {puts "$r ..."}
}
puts "OK, $n is the smallest n such that {$a $n $m} satisfies $lambda"</langsyntaxhighlight>
 
=={{header|Visual Basic .NET}}==
{{trans|C#}}
<langsyntaxhighlight lang="vbnet">Imports System.Numerics
Imports System.Runtime.CompilerServices
Imports System.Threading
Line 2,609:
End Sub
 
End Module</langsyntaxhighlight>
{{out}}
<pre>ord(37) mod 3343 = 1114
Line 2,621:
{{trans|Kotlin}}
{{libheader|Wren-big}}
<langsyntaxhighlight lang="ecmascript">import "/big" for BigInt
 
class PExp {
Line 2,703:
 
moTest.call(BigInt.new(1511678068), BigInt.new(7379191741))
moTest.call(BigInt.new(3047753288), BigInt.new(2257683301))</langsyntaxhighlight>
 
{{out}}
Line 2,720:
 
It would probably be nice to memoize the prime numbers but that isn't necessary for this task.
<langsyntaxhighlight lang="zkl">var BN =Import("zklBigNum");
var Sieve=Import("sieve");
 
Line 2,754:
}
return(res);
}</langsyntaxhighlight>
<langsyntaxhighlight lang="zkl">multiOrder(37,1000).println();
b:=BN(10).pow(20)-1;
multiOrder(2,b).println();
Line 2,763:
[BN(1)..multiOrder(54,b)-1].filter1('wrap(r,b54){b54.powm(r,b)==1},BN(54)) :
if (_) println("Exists a power r < 9090 where (54^r)%b)==1");
else println("Everything checks.");</langsyntaxhighlight>
{{out}}
<pre>
10,333

edits