Modular exponentiation: Difference between revisions

{{trans|D}}

 

BigInt result = 1

 

print(pow_mod(BigInt(‘2988348162058574136915891421498819466320163312926952423791023078876139’),

BigInt(‘2351399303373464486466122544523690094744975233415544072992656881240319’),

 

{{out}}

Using the big integer implementation from a cryptographic library [https://github.com/cforler/Ada-Crypto-Library/].

 

 

procedure Mod_Exp is

Ada.Text_IO.Put("A**B (mod 10**40) = ");

Ada.Text_IO.Put_Line(LN.Utils.To_String(LN.Mod_Utils.Pow((+A), (+B), M)));

 

{{out}}

The code below uses Algol 68 Genie which provides arbitrary precision arithmetic for LONG LONG modes.

 

BEGIN

PR precision=1000 PR

printf (($"Last 40 digits = ", 40dl$, mod power (a, b, m)))

END

 

{{out}}

=={{header|Arturo}}==

 

b: 2351399303373464486466122544523690094744975233415544072992656881240319

 

loop [40 80 180 888] 'm ->

 

{{out}}

=={{header|AutoHotkey}}==

{{libheader|MPL}}

#SingleInstance, Force

SetBatchLines, -1

 

msgbox % MP_DEC(result)

{{out}}

<pre>1527229998585248450016808958343740453059</pre>

{{works with|BBC BASIC for Windows}}

Uses the Huge Integer Math & Encryption library.

PROC_himeinit("")

h1% = 1 : h2% = 2 : h3% = 3 : h4% = 4

SYS `hi_PowMod`, ^h1%, ^h2%, ^h3%, ^h4%

{{out}}

<pre>

=={{header|Bracmat}}==

{{trans|Icon_and_Unicon}}

= base exponent modulus result

. !arg:(?base,?exponent,?modulus)

)

& out$("last 40 digits = " mod-power$(!a,!b,10^40))

{{out}}

<pre>last 40 digits = 1527229998585248450016808958343740453059</pre>

Given numbers are too big for even 64 bit integers, so might as well take the lazy route and use GMP:

{{libheader|GMP}}

 

int main()

 

return 0;

Output:

<pre>

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

We can use the built-in function from BigInteger.

using System.Numerics;

 

Console.WriteLine(BigInteger.ModPow(a, b, m));

}

{{out}}

<pre>

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

{{libheader|Boost}}

#include <boost/multiprecision/cpp_int.hpp>

#include <boost/multiprecision/integer.hpp>

std::cout << powm(a, b, pow(cpp_int(10), 40)) << '\n';

return 0;

 

{{out}}

 

=={{header|Clojure}}==

(defn m* [p q] (mod (* p q) m))

(loop [b b, e e, x 1]

(if (zero? e) x

(if (even? e) (recur (m* b b) (/ e 2) x)

 

(defn modpow

" b^e mod m (using Java which solves some cases the pure clojure method has to be modified to tackle--i.e. with large b & e and

calculation simplications when gcd(b, m) == 1 and gcd(e, m) == 1) "

[b e m]

 

=={{header|Common Lisp}}==

"Return BASE raised to the POWER, modulo DIVISOR.

This function is faster than (MOD (EXPT BASE POWER) DIVISOR), but

(let ((a 2988348162058574136915891421498819466320163312926952423791023078876139)

(b 2351399303373464486466122544523690094744975233415544072992656881240319))

 

{{works with|CLISP}}

(let ((a 2988348162058574136915891421498819466320163312926952423791023078876139)

(b 2351399303373464486466122544523690094744975233415544072992656881240319))

 

===Implementation with LOOP===

(loop with c = 1 while (plusp n) do

(if (oddp n) (setf c (mod (* a c) m)))

(setf n (ash n -1))

(setf a (mod (* a a) m))

 

=={{header|Crystal}}==

 

module Integer

m = 10.to_big_i ** 40

 

 

{{out}}

{{trans|Icon_and_Unicon}}

Compile this module with <code>-version=modular_exponentiation</code> to see the output.

 

private import std.bigint;

"4744975233415544072992656881240319"),

BigInt(10) ^^ 40).writeln;

{{out}}

<pre>1527229998585248450016808958343740453059</pre>

 

=={{header|Dc}}==

=={{header|Delphi}}==

{{libheader| System.SysUtils}}

{{Trans|C#}}

Thanks for Rudy Velthuis, BigIntegers library [https://github.com/rvelthuis/DelphiBigNumbers].

program Modular_exponentiation;

 

Writeln(BigInteger.ModPow(a, b, m).ToString);

readln;

{{out}}

<pre>1527229998585248450016808958343740453059</pre>

 

=={{header|EchoLisp}}==

(lib 'bigint)

 

(xpowmod a b m)

→ 1527229998585248450016808958343740453059

 

=={{header|Emacs Lisp}}==

{{libheader|Calc}}

(b "2351399303373464486466122544523690094744975233415544072992656881240319"))

;; "$ ^ $$ mod (10 ^ 40)" performs modular exponentiation.

;; "unpack(-5, x)_1" unpacks the integer from the modulo form.

 

=={{header|Erlang}}==

%%% For details of the algorithms used see

%%% https://en.wikipedia.org/wiki/Modular_exponentiation

binary_exp(10,40)).

 

<pre>

34> modexp_rosetta:test().

 

=={{header|F_Sharp|F#}}==

let rec loop a b c =

if b = 0I then c else

let b = 2351399303373464486466122544523690094744975233415544072992656881240319I

printfn "%A" (expMod a b (10I**40)) // -> 1527229998585248450016808958343740453059

 

=={{header|Factor}}==

2988348162058574136915891421498819466320163312926952423791023078876139

2351399303373464486466122544523690094744975233415544072992656881240319

10 40 ^

{{out}}

<pre>

 

=={{header|FreeBASIC}}==

'From first principles (No external library)

 

<pre>

Result:

 

=={{header|Frink}}==

b = 2351399303373464486466122544523690094744975233415544072992656881240319

 

{{out}}

 

=={{header|GAP}}==

a := 2988348162058574136915891421498819466320163312926952423791023078876139;

b := 2351399303373464486466122544523690094744975233415544072992656881240319;

end;

 

 

=={{header|gnuplot}}==

 

powm(b, e, m) = _powm(b, e, m, 1)

# Usage

print powm(2, 3453, 131)

 

=={{header|Go}}==

 

import (

r.Exp(a, b, m)

fmt.Println(r)

{{out}}

<pre>

 

=={{header|Groovy}}==

2351399303373464486466122544523690094744975233415544072992656881240319,

Ouput:

<pre>1527229998585248450016808958343740453059</pre>

 

=={{header|Haskell}}==

modPow :: Integer -> Integer -> Integer -> Integer -> Integer

modPow b e 1 r = 0

(10 ^ 40)

1)

{{out}}

<pre>1527229998585248450016808958343740453059</pre>

 

or in terms of ''until'':

powerMod b e m = x

where

2988348162058574136915891421498819466320163312926952423791023078876139

2351399303373464486466122544523690094744975233415544072992656881240319

{{Out}}

<pre>1527229998585248450016808958343740453059</pre>

=={{header|Icon}} and {{header|Unicon}}==

This uses the exponentiation procedure from [[RSA_code#Icon_and_Unicon|RSA Code]] an example of the right to left binary method.

a := 2988348162058574136915891421498819466320163312926952423791023078876139

b := 2351399303373464486466122544523690094744975233415544072992656881240319

}

return result

 

{{out}}

 

=={{header|J}}==

b =: 2351399303373464486466122544523690094744975233415544072992656881240319x

m =: 10^40x

 

a m&|@^ b

'''Discussion''': The phrase <tt>a m&|@^ b</tt> is the natural expression of <tt>a^b mod m</tt> in J, and is recognized by the interpreter as an opportunity for optimization, by [http://www.jsoftware.com/help/dictionary/special.htm#recognized%20phrase avoiding the exponentiation].

 

<code>java.math.BigInteger.modPow</code> solves this task. Inside [[OpenJDK]], [http://hg.openjdk.java.net/jdk7/jdk7/jdk/file/f097ca2434b1/src/share/classes/java/math/BigInteger.java BigInteger.java] implements <code>BigInteger.modPow</code> with a fast algorithm from [http://philzimmermann.com/EN/bnlib/index.html Colin Plumb's bnlib]. This "window algorithm" caches odd powers of the base, to decrease the number of squares and multiplications. It also exploits both the Chinese remainder theorem and the [[Montgomery reduction]].

 

 

public class PowMod {

System.out.println(a.modPow(b, m));

}

{{out}}

<pre>1527229998585248450016808958343740453059</pre>

We can use the built-in <code>powermod</code> function with the built-in <code>BigInt</code> type (based on GMP):

 

b = 2351399303373464486466122544523690094744975233415544072992656881240319

m = big(10) ^ 40

 

{{out}}

 

=={{header|Kotlin}}==

 

import java.math.BigInteger

val m = BigInteger.TEN.pow(40)

println(a.modPow(b, m))

 

{{out}}

Following scheme

 

We will call the lib_BN library for big numbers:

 

{BN.pow 10 40}}

-> 1527229998585248450016808958343740453059 // 3300ms

 

=={{header|Maple}}==

b := 2351399303373464486466122544523690094744975233415544072992656881240319:

{{out}}

<pre>1527229998585248450016808958343740453059</pre>

 

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

b = 2351399303373464486466122544523690094744975233415544072992656881240319;

m = 10^40;

PowerMod[a, b, m]

 

=={{header|Maxima}}==

b: 2351399303373464486466122544523690094744975233415544072992656881240319$

power_mod(a, b, 10^40);

 

=={{header|Nim}}==

{{libheader|bigints}}

 

proc powmod(b, e, m: BigInt): BigInt =

b = initBigInt("2351399303373464486466122544523690094744975233415544072992656881240319")

 

{{out}}

<pre>1527229998585248450016808958343740453059</pre>

Using the zarith library:

 

let a = Z.of_string "2988348162058574136915891421498819466320163312926952423791023078876139" in

let b = Z.of_string "2351399303373464486466122544523690094744975233415544072992656881240319" in

Z.powm a b m

|> Z.to_string

{{out}}

<pre>1527229998585248450016808958343740453059</pre>

Usage : a b mod powmod

 

1 exponent dup ifZero: [ return ]

while ( dup 0 > ) [

dup isEven ifFalse: [ swap base * modulus mod swap ]

2 / base sq modulus mod ->base

 

{{out}}

 

=={{header|ooRexx}}==

 

numeric digits 100

base = (base * base) // modulus

end

{{out}}

<pre>

 

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

b=2351399303373464486466122544523690094744975233415544072992656881240319;

 

=={{header|Pascal}}==

{{libheader|GMP}}

A port of the C example using gmp.

 

uses

mpz_clear(m);

mpz_clear(r);

{{out}}

<pre>% ./ModularExponentiation

=={{header|Perl}}==

Calculating the result both with an explicit algorithm (borrowed from Raku example) and with a built-in available when the <code>use bigint</code> pragma is invoked. Note that <code>bmodpow</code> modifies the base value (here <code>$a</code>) while <code>expmod</code> does not.

 

sub expmod {

 

print expmod($a, $b, $m), "\n";

{{out}}

<pre>1527229998585248450016808958343740453059

Already builtin as mpz_powm, but here is an explicit version

 

<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;">mpz_powm</span><span style="color: #0000FF;">(</span><span style="color: #000000;">result</span><span style="color: #0000FF;">,</span><span style="color: #000000;">base</span><span style="color: #0000FF;">,</span><span style="color: #000000;">exponent</span><span style="color: #0000FF;">,</span><span style="color: #000000;">modulus</span><span style="color: #0000FF;">)</span>

<span style="color: #0000FF;">?</span><span style="color: #7060A8;">mpz_get_str</span><span style="color: #0000FF;">(</span><span style="color: #000000;">result</span><span style="color: #0000FF;">)</span>

 

{{out}}

 

=={{header|PHP}}==

$a = '2988348162058574136915891421498819466320163312926952423791023078876139';

$b = '2351399303373464486466122544523690094744975233415544072992656881240319';

$m = '1' . str_repeat('0', 40);

{{out}}

<pre>1527229998585248450016808958343740453059</pre>

=={{header|PicoLisp}}==

The following function is taken from "lib/rsa.l":

(let M 1

(loop

(T (=0 (setq Y (>> 1 Y)))

M )

Test:

2988348162058574136915891421498819466320163312926952423791023078876139

2351399303373464486466122544523690094744975233415544072992656881240319

10000000000000000000000000000000000000000 )

 

=={{header|Prolog}}==

{{works with|SWI Prolog}}

SWI Prolog has a built-in function named powm for this purpose.

A = 2988348162058574136915891421498819466320163312926952423791023078876139,

B = 2351399303373464486466122544523690094744975233415544072992656881240319,

M is 10 ** 40,

P is powm(A, B, M),

 

{{out}}

 

=={{header|Python}}==

b = 2351399303373464486466122544523690094744975233415544072992656881240319

m = 10 ** 40

{{out}}

<pre>1527229998585248450016808958343740453059</pre>

 

" Without using builtin function "

x = 1

b = 2351399303373464486466122544523690094744975233415544072992656881240319

m = 10 ** 40

{{out}}

<pre>1527229998585248450016808958343740453059</pre>

=={{header|Quackery}}==

 

[ dup while

dup 1 & if

2988348162058574136915891421498819466320163312926952423791023078876139

2351399303373464486466122544523690094744975233415544072992656881240319

 

{{out}}

 

=={{header|Racket}}==

#lang racket

(require math)

(define m (expt 10 40))

(modular-expt a b m)

{{out}}

<pre>

(formerly Perl 6)

This is specced as a built-in, but here's an explicit version:

my $c = 1;

repeat while $b div= 2 {

2988348162058574136915891421498819466320163312926952423791023078876139,

2351399303373464486466122544523690094744975233415544072992656881240319,

{{out}}

<pre>1527229998585248450016808958343740453059</pre>

This REXX program code has code to &nbsp; automatically &nbsp; adjust the number of decimal digits to accommodate huge

<br>numbers which are computed when raising large numbers to some arbitrary power.

parse arg a b m /*obtain optional args from the CL*/

if a=='' | a=="," then a= 2988348162058574136915891421498819466320163312926952423791023078876139

if p // 2 then $= $ * x // mm /*is P odd? (is ÷ remainder ≡ 1?)*/

p= p % 2; x= x * x // mm /*halve P; calculate x² mod n */

This REXX program makes use of &nbsp; '''LINESIZE''' &nbsp; REXX program (or BIF) which is used to determine the screen width (or linesize) of the terminal (console).

<br>The BIF is used to determine the width of a line separator &nbsp; (which are used to separate different outputs).

===version 2===

This REXX version handles only up to 100 decimal digits.

/* REXX Modular exponentiation */

 

base = (base * base) // modulus

end

{{out}}

<pre>

=={{header|Ruby}}==

===Built in since version 2.5.===

b = 2351399303373464486466122544523690094744975233415544072992656881240319

m = 10**40

===Using OpenSSL standard library===

{{libheader|OpenSSL}}

a = 2988348162058574136915891421498819466320163312926952423791023078876139

b = 2351399303373464486466122544523690094744975233415544072992656881240319

m = 10 ** 40

===Written in Ruby===

def mod_exp(n, e, mod)

fail ArgumentError, 'negative exponent' if e < 0

prod

end

 

=={{header|Rust}}==

num = "0.2.0"

*/

base %= &m;

}

 

'''Test code:'''

 

let (a, b, num_digits) = (

"2988348162058574136915891421498819466320163312926952423791023078876139",

println!("The last {} digits of\n{}\nto the power of\n{}\nare:\n{}",

num_digits, a, b, result);

{{out}}

<pre>The last 40 digits of

 

=={{header|Scala}}==

 

val a = BigInt(

"2351399303373464486466122544523690094744975233415544072992656881240319")

 

 

=={{header|Scheme}}==

 

(define (square n)

(* n n))

(mod-exp 2988348162058574136915891421498819466320163312926952423791023078876139

2351399303373464486466122544523690094744975233415544072992656881240319

 

{{out}}

[http://seed7.sourceforge.net/libraries/bigint.htm#modPow%28in_var_bigInteger,in_var_bigInteger,in_bigInteger%29 modPow],

which does modular exponentiation.

include "bigint.s7i";

 

2351399303373464486466122544523690094744975233415544072992656881240319_,

10_ ** 40));

 

{{out}}

 

The library bigint.s7i defines modPow with:

in var bigInteger: exponent, in bigInteger: modulus) is func

result

end while;

end if;

 

Original source: [http://seed7.sourceforge.net/algorith/math.htm#modPow]

=={{header|Sidef}}==

Built-in:

2988348162058574136915891421498819466320163312926952423791023078876139,

2351399303373464486466122544523690094744975233415544072992656881240319,

 

User-defined:

var c = 1

do {

} while (b //= 2)

c

{{out}}

<pre>

AttaSwift's BigInt has a built-in modPow method, but here we define a generic modPow.

 

 

func modPow<T: BinaryInteger>(n: T, e: T, m: T) -> T {

let b = BigInt("2351399303373464486466122544523690094744975233415544072992656881240319")

 

 

{{out}}

 

===Recursive===

 

# Algorithm from http://introcs.cs.princeton.edu/java/78crypto/ModExp.java.html

}

return $c

Demonstrating:

set b 2351399303373464486466122544523690094744975233415544072992656881240319

set n [expr {10**40}]

{{out}}

<pre>

 

===Iterative===

proc modexp {a b n} {

for {set c 1} {$b} {set a [expr {$a*$a % $n}]} {

}

return $c

Demonstrating:

set b 2351399303373464486466122544523690094744975233415544072992656881240319

set n [expr {10**40}]

{{out}}

<pre>

From your system prompt:

 

2351399303373464486466122544523690094744975233415544072992656881240319

(expt 10 40)))'

 

=={{header|Visual Basic .NET}}==

{{works with|Visual Basic .NET|2011}}

Imports System.Numerics

 

Loop

Return result

{{out}}

<pre>

=={{header|Wren}}==

{{libheader|Wren-big}}

 

var a = BigInt.new("2988348162058574136915891421498819466320163312926952423791023078876139")

var b = BigInt.new("2351399303373464486466122544523690094744975233415544072992656881240319")

var m = BigInt.ten.pow(40)

 

{{out}}

=={{header|zkl}}==

Using the GMP big num library:

a:=BN("2988348162058574136915891421498819466320163312926952423791023078876139");

b:=BN("2351399303373464486466122544523690094744975233415544072992656881240319");

m:=BN(10).pow(40);

a.powm(b,m).println();

{{out}}

<pre>