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;

 

=={{header|C sharp|C#}}==

{{trans|Java}}

using System.Collections.Generic;

using System.Numerics;

}

}

{{out}}

<pre>ord(37) mod 3343 = 1114

=={{header|C++}}==

{{trans|C}}

#include <bitset>

#include <iostream>

 

return 0;

{{out}}

<pre>100

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

(map (partial ord' a))

(reduce lcm))))

{{out}}

<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

 

=={{header|Factor}}==

{{works with|Factor|0.99 2020-01-23}}

 

: (ord) ( a pair -- n )

2dup gcd nip 1 =

[ group-factors [ (ord) ] with [ lcm ] map-reduce ]

{{out}}

<pre>

 

=={{header|Go}}==

 

import (

}

return a.SetInt64(0)

{{out}}

<pre>

Assuming a function

 

:: (Integral a, Integral b)

=> a -> a -> b -> a

| even i = g (b * b `rem` m) (i `quot` 2)

| otherwise = f b (i - 1) (b * y `rem` m)

 

to efficiently calculate powers modulo some <code>Integral</code>, we get

 

 

foldl1_ = foldl1' --'

where

x = powerMod pk a (t `div` (q ^ e))

 

=={{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]].)

 

function factors(n)

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

 

=={{header|Nim}}==

{{trans|Kotlin}}

{{libheader|bignum}}

import bignum

 

moTest(newInt("1511678068"), newInt("7379191741"))

 

 

{{out}}

 

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

 

=={{header|Perl}}==

Using modules:

{{libheader|ntheory}}

say znorder(54, 100001);

or

say znorder(Mod(54, 100001));

 

=={{header|Phix}}==

{{trans|Ruby}}

{{libheader|Phix/mpfr}}

{{out}}

<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

 

=={{header|Raku}}==

(formerly Perl 6)

 

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;

@qs = flat @qs.map(-> $q { (0..$f.value).map(-> $j { $q * $f.key ** $j }) });

}

}

sub mo($a, $m) {

}

use Test;

for (10, 21, 25, 150, 1231, 123141, 34131) -> $n {

}

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

$b = 100001;

is mo(54, $b), 9090, 'mo(54,100001) == 9090';

{{out}}

<pre>ok 1 - 10 factors correctly

 

=={{header|REXX}}==

wa= 0; wm= 0 /* ═a═ ══m══ */ /*maximum widths of the A and M values.*/

@.=.; @.1= 3 10

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

end /*j*/

{{out|output|.}}

<pre>

=={{header|Ruby}}==

 

 

def powerMod(b, p, m)

else

puts 'Everything checks.'

 

{{out}}

 

=={{header|Seed7}}==

include "bigint.s7i";

 

moTest(1511678068_, 7379191741_);

moTest(3047753288_, 2257683301_);

 

{{out}}

 

Built-in:

 

{{trans|Raku}}

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|Visual Basic .NET}}==

{{trans|C#}}

Imports System.Runtime.CompilerServices

Imports System.Threading

End Sub

 

{{out}}

<pre>ord(37) mod 3343 = 1114

{{trans|Kotlin}}

{{libheader|Wren-big}}

 

class PExp {

 

moTest.call(BigInt.new(1511678068), BigInt.new(7379191741))

 

{{out}}

 

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>