Multiplicative order: Difference between revisions

{{trans|D}}

 

BigInt prime

Int exp

 

moTest(1511678068, 7379191741)

 

{{out}}

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

printf("%lu\n", multi_order(54, 100001));

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

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

 

=={{header|Mathematica}}/{{header|Wolfram Language}}==

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}}

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

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

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

$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>