Multiplicative order: Difference between revisions
m
syntax highlighting fixup automation
Alextretyak (talk | contribs) (Added 11l) |
Thundergnat (talk | contribs) m (syntax highlighting fixup automation) |
||
Line 49:
{{trans|D}}
<
BigInt prime
Int exp
Line 125:
moTest(1511678068, 7379191741)
moTest(BigInt(‘3047753288’), BigInt(‘2257683301’))</
{{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").
<
type Positive_Array is array (Positive range <>) of Positive;
Line 159:
-- (2) 1 < Coprime_Factors(I) for all I
end Multiplicative_Order;</
Here is the implementation ("multiplicative_order.adb"):
<
function Find_Order(Element, Modulus: Positive) return Positive is
Line 228:
end Find_Order;
end Multiplicative_Order;</
This is a sample program using the Multiplicative_Order package:
<
procedure Main is
Line 254:
-- it gives an incorrect result
IIO.Put(Find_Order(37, (11, 19, 8, 2)));
end Main;</
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 }} -->
<
MODE POWMODSTRUCT = LONG INT;
Line 388:
printf(($g$, "Everything checks.", $l$))
FI
)</
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.
<
{
ulong r = 1;
Line 463:
printf("%lu\n", multi_order(54, 100001));
return 0;
}</
=={{header|C sharp|C#}}==
{{trans|Java}}
<
using System.Collections.Generic;
using System.Numerics;
Line 655:
}
}
}</
{{out}}
<pre>ord(37) mod 3343 = 1114
Line 666:
=={{header|C++}}==
{{trans|C}}
<
#include <bitset>
#include <iostream>
Line 804:
return 0;
}</
{{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.
<
(if (zero? b)
a
Line 837:
(map (partial ord' a))
(reduce lcm))))
</syntaxhighlight>
{{out}}
<pre>
Line 846:
=={{header|D}}==
{{trans|Java}}
<
import std.random;
import std.stdio;
Line 1,001:
moTest(1511678068, 7379191741);
moTest(3047753288, 2257683301);
}</
{{out}}
<pre>ord(37) mod 3343 = 1114
Line 1,011:
=={{header|EchoLisp}}==
<
(require 'bigint)
Line 1,044:
(order (+ (expt 10 1000) 1) 15485863)
→ 15485862
</syntaxhighlight>
=={{header|Factor}}==
{{works with|Factor|0.99 2020-01-23}}
<
: (ord) ( a pair -- n )
Line 1,058:
2dup gcd nip 1 =
[ group-factors [ (ord) ] with [ lcm ] map-reduce ]
[ 2drop 0/0. ] if ;</
{{out}}
<pre>
Line 1,068:
=={{header|Go}}==
<
import (
Line 1,169:
}
return a.SetInt64(0)
}</
{{out}}
<pre>
Line 1,184:
Assuming a function
<
:: (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"</
to efficiently calculate powers modulo some <code>Integral</code>, we get
<
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</
=={{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.
<
a=. x: x
m=. x: y
assert. 1=a+.m
*./ a mopk"1 |: __ q: m
)</
The dyadic verb ''mopk'' expects a pair of prime and exponent
Line 1,238:
exponents ''q^d'' into a product.
<
a=. x: x
'p k'=. x: y
Line 1,247:
d=. (1<x)+x (pm i. 1:)&> (e-1) */\@$&.> q
*/q^d
)</
For example:
<
100
2 mo _1+10^80x
190174169488577769580266953193403101748804183400400</
=={{header|Java}}==
{{trans|Kotlin}}
<
import java.util.ArrayList;
import java.util.List;
Line 1,363:
moTest(BigInteger.valueOf(3047753288L), BigInteger.valueOf(2257683301L));
}
}</
{{out}}
<pre>ord(37) mod 3343 = 1114
Line 1,374:
=={{header|Julia}}==
(Uses the <code>factors</code> function from [[Factors of an integer#Julia]].)
<
function factors(n)
Line 1,398:
end
res
end</
Example output (using <code>big</code> to employ arbitrary-precision arithmetic where needed):
Line 1,417:
=={{header|Kotlin}}==
{{trans|Go}}
<
import java.math.BigInteger
Line 1,510:
moTest(BigInteger("1511678068"), BigInteger("7379191741"))
moTest(BigInteger("3047753288"), BigInteger("2257683301"))
}</
{{out}}
Line 1,523:
=={{header|Maple}}==
<
For example,
<
100</
=={{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:
<
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]</
gives back:
<pre>100
Line 1,548:
=={{header|Maxima}}==
<
/* 100 */
Line 1,564:
zn_order(11, 1 + 10^100);
/* 2583496112724752500580158969425549088007844580826869433740066152289289764829816356800 */</
=={{header|Nim}}==
{{trans|Kotlin}}
{{libheader|bignum}}
<
import bignum
Line 1,652:
moTest(newInt("1511678068"), newInt("7379191741"))
moTest(newInt("3047753288"), newInt("2257683301"))</
{{out}}
Line 1,663:
=={{header|PARI/GP}}==
<syntaxhighlight lang
=={{header|Perl}}==
Using modules:
{{libheader|ntheory}}
<
say znorder(54, 100001);
use bigint; say znorder(11, 1 + 10**100);</
or
<
say znorder(Mod(54, 100001));
say znorder(Mod(11, 1 + Math::Pari::PARI(10)**100));</
=={{header|Phix}}==
{{trans|Ruby}}
{{libheader|Phix/mpfr}}
<!--<
<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>
<!--</
{{out}}
<pre>
Line 1,817:
=={{header|Python}}==
<
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.'</
=={{header|Racket}}==
Line 1,889:
shown below.
<
#lang racket
(require math)
Line 1,915:
(order (- (expt 10 10000) 1) 22801763489)
(order 13 (+ 1 (expt 10 80)))
</syntaxhighlight>
Output:
<
100
3959
Line 1,923:
22801763488
109609547199756140150989321269669269476675495992554276140800
</syntaxhighlight>
=={{header|Raku}}==
(formerly Perl 6)
<syntaxhighlight lang="raku"
sub mo-prime($a, $p, $e) {
Line 1,958:
$b = 100001;
is mo(54, $b), 9090, 'mo(54,100001) == 9090';
}</
{{out}}
<pre>ok 1 - 10 factors correctly
Line 1,973:
=={{header|REXX}}==
<
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. */</
{{out|output|.}}
<pre>
Line 2,012:
=={{header|Ruby}}==
<
def powerMod(b, p, m)
Line 2,052:
else
puts 'Everything checks.'
end</
{{out}}
Line 2,065:
=={{header|Seed7}}==
<
include "bigint.s7i";
Line 2,182:
moTest(1511678068_, 7379191741_);
moTest(3047753288_, 2257683301_);
end func;</
{{out}}
Line 2,197:
Built-in:
<
say 54.znorder(100001) #=> 9090</
{{trans|Raku}}
<
var m = p**e
var t = (p-1)*(p**(e-1))
Line 2,226:
say mo(2, b)
say mo(17, b)
}</
{{out}}
<pre>
Line 2,238:
{{trans|Python}}
{{tcllib|struct::list}}
<
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"</
=={{header|Visual Basic .NET}}==
{{trans|C#}}
<
Imports System.Runtime.CompilerServices
Imports System.Threading
Line 2,609:
End Sub
End Module</
{{out}}
<pre>ord(37) mod 3343 = 1114
Line 2,621:
{{trans|Kotlin}}
{{libheader|Wren-big}}
<
class PExp {
Line 2,703:
moTest.call(BigInt.new(1511678068), BigInt.new(7379191741))
moTest.call(BigInt.new(3047753288), BigInt.new(2257683301))</
{{out}}
Line 2,720:
It would probably be nice to memoize the prime numbers but that isn't necessary for this task.
<
var Sieve=Import("sieve");
Line 2,754:
}
return(res);
}</
<
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.");</
{{out}}
<pre>
|