Multiplicative order: Difference between revisions

{{task|Discrete math}}

The '''multiplicative order''' of ''a'' relative to ''m'' is the least positive integer ''n'' such that ''a^n'' is 1 (modulo ''m'').

 

One possible algorithm that is efficient also for large numbers is the following: By the [[wp:Chinese_Remainder_Theorem|Chinese Remainder Theorem]], it's enough to calculate the multiplicative order for each prime exponent ''p^k'' of ''m'', and

combine the results with the ''[[least common multiple]]'' operation.

 

Implement a routine to calculate the multiplicative order along these lines. You may assume that routines to determine the factorization into prime powers are available in some library.

 

 

<p>Suppose you are given a prime<tt> p </tt>and a complete factorization

element<tt> a </tt>in<tt> (Z/(p))^* </tt>using<tt> O((lg p)⁴/(lg lg p)) </tt>bit

operations.</p>

<p>Let the prime factorization of<tt> p-1 </tt> be<tt> q1^e1q2^e2...qk^ek</tt> .<tt> </tt>We use the following observation:

if<tt> x^((p-1)/qi^fi) = 1 (mod p)</tt> ,<tt> </tt>

 

Hence it suffices to find, for each<tt> i</tt> ,<tt> </tt>the exponent<tt> fi </tt> such that the condition above holds.</p>

Finally, for each<tt> i</tt> ,<tt> </tt>repeatedly raise<tt> xi </tt>to the<tt> qi</tt>-th power<tt> (mod p) </tt>(as many as<tt> ei-1 </tt> times), checking to see when 1 is obtained.

This can be done using<tt> O((lg p)³) </tt>steps.

 

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

=={{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|Julia}}==

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

end

end

 

end

res

 

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

</pre>

 

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

 

=={{header|PARI/GP}}==

 

{{out}}

 

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

 

=={{header|Ruby}}==

 

 

def powerMod(b, p, m)

result = (result * result) % m

end

end

 

r = 1

for q, e in t.prime_division

while x != 1

r *= q

 

def multOrder(a, m)

result.lcm(multOrder_(a, *f))

end

 

b = 10**20-1

b = 100001

puts multOrder(54,b)

else

puts 'Everything checks.'

 

=={{header|Tcl}}==

{{trans|Python}}

{{tcllib|struct::list}}

package require struct::list

 

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

}