Multiplicative order: Difference between revisions

The total cost is dominated by<tt> O(k(lg p)³)</tt> ,<tt> </tt>which is<tt> O((lg p)⁴/(lg lg p))</tt>.

<br><br>

 

=={{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;

-- (2) 1 < Coprime_Factors(I) for all I

 

 

Here is the implementation ("multiplicative_order.adb"):

 

 

function Find_Order(Element, Modulus: Positive) return Positive is

end Find_Order;

 

 

This is a sample program using the Multiplicative_Order package:

 

procedure Main is

-- it gives an incorrect result

IIO.Put(Find_Order(37, (11, 19, 8, 2)));

 

The output from the sample program:

{{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;

printf(($g$, "Everything checks.", $l$))

FI

Output:

<pre>

=={{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;

{

sieve();

return 0;

 

{{trans|Java}}

using System.Collections.Generic;

using System.Numerics;

}

}

{{out}}

<pre>ord(37) mod 3343 = 1114

ord(1511678068) mod 7379191741 = 614932645

ord(3047753288) mod 2257683301 = 62713425</pre>

 

=={{header|D}}==

{{trans|Java}}

import std.random;

import std.stdio;

moTest(1511678068, 7379191741);

moTest(3047753288, 2257683301);

{{out}}

<pre>ord(37) mod 3343 = 1114

 

=={{header|EchoLisp}}==

(require 'bigint)

 

(order (+ (expt 10 1000) 1) 15485863)

→ 15485862

 

 

 

{{out}}

<pre>

100

</pre>

 

=={{header|Go}}==

 

import (

}

return a.SetInt64(0)

{{out}}

<pre>

Assuming a function

 

 

 

 

 

 

 

=={{header|J}}==

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

exponents ''q^d'' into a product.

 

a=. x: x

'p k'=. x: y

d=. (1<x)+x (pm i. 1:)&> (e-1) */\@$&.> q

*/q^d

 

For example:

 

100

2 mo _1+10^80x

 

=={{header|Java}}==

{{trans|Kotlin}}

import java.util.ArrayList;

import java.util.List;

moTest(BigInteger.valueOf(3047753288L), BigInteger.valueOf(2257683301L));

}

{{out}}

<pre>ord(37) mod 3343 = 1114

ord(1511678068) mod 7379191741 = 614932645

ord(3047753288) mod 2257683301 = 62713425</pre>

 

=={{header|Julia}}==

(Uses the <code>factors</code> function from [[Factors of an integer#Julia]].)

f = [one(n)]

for (p,e) in factor(n)

end

return length(f) == 1 ? [one(n), n] : sort!(f)

end

res

 

Example output (using <code>big</code> to employ arbitrary-precision arithmetic where needed):

=={{header|Kotlin}}==

{{trans|Go}}

 

import java.math.BigInteger

moTest(BigInteger("1511678068"), BigInteger("7379191741"))

moTest(BigInteger("3047753288"), BigInteger("2257683301"))

 

{{out}}

 

=={{header|Maple}}==

For example,

 

In Mathematica this is really easy, as this function is built-in:

MultiplicativeOrder[k,n] gives the multiplicative order of k modulo n, defined as the smallest integer m such that k^m == 1 mod n.<br>

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]

gives back:

<pre>100

 

=={{header|Maxima}}==

/* 100 */

 

 

zn_order(11, 1 + 10^100);

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

{{out}}

ord([big]) mod 7919 = 3959

ord([big]) mod 15485863 = 15485862

ord([big]) mod 22801763489 = 22801763488

ord(1511678068) mod 7379191741 = 614932645

ord(3047753288) mod 2257683301 = 62713425

ord(17) mod 99999999999999999999 = 1499522760

ord(54) mod 100001 = 9090

</pre>

 

=={{header|Python}}==

 

while b != 0:

a, b = b, a % b

print 'Exists a power r < 9090 where pow(54,r,b)==1'

else:

 

=={{header|Racket}}==

shown below.

 

#lang racket

(require math)

(order (- (expt 10 10000) 1) 22801763489)

(order 13 (+ 1 (expt 10 80)))

Output:

100

3959

22801763488

109609547199756140150989321269669269476675495992554276140800

 

 

do w=1 for 2 /*when W≡1, find max widths of A and M.*/

numeric digits d /*start with 100 decimal digits. */

parse var p 'E' _ /*try to extract the exponent from P. */

if _\=='' then do; numeric digits _+d /*bump the decimal digs.*/

p=r*a /*recalculate integer P.*/

end

end /*n*/ /* [↑] // is really ÷ remainder.*/

say pad 'a=' right(a,wa) pad "m=" right(m,wm) pad 'multiplicative order:' n

end /*j*/

<pre>

a= 3 m= 10 multiplicative order: 4

=={{header|Ruby}}==

 

 

def powerMod(b, p, m)

else

puts 'Everything checks.'

 

{{out}}

 

=={{header|Seed7}}==

include "bigint.s7i";

 

moTest(1511678068_, 7379191741_);

moTest(3047753288_, 2257683301_);

 

{{out}}

 

=={{header|Sidef}}==

var m = p**e

var t = (p-1)*(p**(e-1))

say mo(2, b)

say mo(17, b)

{{out}}

<pre>

{{trans|Python}}

{{tcllib|struct::list}}

package require struct::list

 

if {$r % 1000 == 0} {puts "$r ..."}

}

 

=={{header|zkl}}==

 

It would probably be nice to memoize the prime numbers but that isn't necessary for this task.

var Sieve=Import("sieve");

 

}

return(res);

b:=BN(10).pow(20)-1;

multiOrder(2,b).println();

[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");

{{out}}

<pre>