Modular inverse: Difference between revisions

{{trans|C}}

 

V b0 = b

V x0 = 0

R x1

 

 

{{out}}

 

=={{header|8th}}==

\ return "extended gcd" of a and b; The result satisfies the equation:

\ a*x + b*y = gcd(a,b)

 

42 2017 n:invmod . cr bye

{{out}}

<pre>

 

=={{header|Action!}}==

INT t,nt,r,nr,q,tmp

 

Test(-486,217)

Test(40,2018)

{{out}}

[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Modular_inverse.png Screenshot from Atari 8-bit computer]

=={{header|Ada}}==

 

with Ada.Text_IO;use Ada.Text_IO;

procedure modular_inverse is

exception when others => Put_Line ("The inverse doesn't exist.");

end modular_inverse;

 

=={{header|ALGOL 68}}==

BEGIN

PROC modular inverse = (INT a, m) INT :

CO

END

{{out}}

<pre>42 ^ -1 (mod 2017) = 1969

{{trans|D}}

 

if b = 1 -> return 1

 

]

 

 

{{out}}

=={{header|AutoHotkey}}==

Translation of [http://rosettacode.org/wiki/Modular_inverse#C C].

 

ModInv(a, b) {

x1 += b0

return x1

{{out}}

<pre>1969</pre>

 

=={{header|AWK}}==

# syntax: GAWK -f MODULAR_INVERSE.AWK

# converted from C

return(x1)

}

{{out}}

<pre>

==={{header|ASIC}}===

{{trans|Pascal}}

REM Modular inverse

E = 42

ModInv = D

RETURN

{{out}}

<pre>

{{works with|Commodore BASIC|3.5}}

{{works with|Nascom ROM BASIC|4.7}}

10 REM Modular inverse

20 LET E = 42

600 LET M = D

610 RETURN

 

=={{header|Batch File}}==

 

{{trans|Perl}}

setlocal enabledelayedexpansion

%== Calls the "function" ==%

if !t! lss 0 set /a t+=b

set %3=!t!

{{Out}}

<pre>1969

 

=={{header|BCPL}}==

 

let mulinv(a, b) =

show(-486, 217)

show(40, 2018)

{{out}}

<pre>42, 2017 -> 1969

=={{header|Bracmat}}==

{{trans|Julia}}

= a b b0 x0 x1 q

. !arg:(?a.?b)

)

& out$(mod-inv$(42.2017))

Output

<pre>1969</pre>

 

=={{header|C}}==

 

int mul_inv(int a, int b)

printf("%d\n", mul_inv(42, 2017));

return 0;

 

The above method has some problems. Most importantly, when given a pair (a,b) with no solution, it generates an FP exception. When given <tt>b=1</tt>, it returns 1 which is not a valid result mod 1. When given negative a or b the results are incorrect. The following generates results that should match Pari/GP for numbers in the int range.

{{trans|Perl}}

 

int mul_inv(int a, int b)

printf("%d\n", mul_inv(40, 2018));

return 0;

{{out}}

<pre>

 

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

{

static void Main()

return x < 0 ? x + m0 : x;

}

 

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

===Iterative implementation===

{{trans|C}}

int mul_inv(int a, int b)

std::cout << mul_inv(42, 2017) << std::endl;

return 0;

 

===Recursive implementation===

 

short ObtainMultiplicativeInverse(int a, int b, int s0 = 1, int s1 = 0)

std::cout << ObtainMultiplicativeInverse(42, 2017) << std::endl;

return 0;

 

=={{header|Clojure}}==

(:require [clojure.math.numeric-tower :as math]))

 

(println (mul_inv 40 2018))

 

 

'''Output:'''

=={{header|CLU}}==

{{trans|Perl}}

if b<0 then b := -b end

if a<0 then a := b - (-a // b) end

end

end

{{out}}

<pre>42, 2017 -> 1969

 

=={{header|Comal}}==

0020 IF b#<0 THEN b#:=-b#

0030 IF a#<0 THEN a#:=b#-(-a# MOD b#)

0190 END

0200 //

{{out}}

<pre>42, 2017 -> 1969

 

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

;;

;; Calculates the GCD of a and b based on the Extended Euclidean Algorithm. The function also returns

(unless (= 1 r) (error "invmod: Values ~a and ~a are not coprimes." a m))

s))

 

{{out}}

 

=={{header|Cowgol}}==

 

sub mulinv(a: int32, b: int32): (t: int32) is

print_nl();

i := i + 1;

{{out}}

<pre>42, 2017 -> 1969

=={{header|Crystal}}==

{{trans|Ruby}}

return 1 if m0 == 1

a, m = a0, m0

inv += m0 if inv < 0

inv

 

{{out}}

=={{header|D}}==

{{trans|C}}

if (b == 1)

return 1;

import std.stdio;

writeln(modInverse(42, 2017));

{{out}}

<pre>1969</pre>

{{trans|C}}

This solution prints the inverse <code>u</code> only if it exists (<code>a*u = 1 mod m</code>).

dc -e "[m=]P?dsm[a=]P?dsa1sv[dsb~rsqlbrldlqlv*-lvsdsvd0<x]dsxxldd[dlmr+]sx0>xdla*lm%[p]sx1=x"

If <code>~</code> is not implemented, it can be replaced by <code>SdSnlnld/LnLd%</code>.

 

 

=={{header|Draco}}==

int t, nt, r, nr, q, tmp;

if b<0 then b := -b fi;

show(-486, 217);

show(40, 2018)

{{out}}

<pre> 42, 2017 -> 1969

 

=={{header|EchoLisp}}==

(lib 'math) ;; for egcd = extended gcd

 

(mod-inv 42 666)

🔴 error: not-coprimes (42 666)

 

=={{header|Elixir}}==

{{trans|Ruby}}

def extended_gcd(a, b) do

{last_remainder, last_x} = extended_gcd(abs(a), abs(b), 1, 0, 0, 1)

end

 

 

{{out}}

 

=={{header|ERRE}}==

 

!$INTEGER

MUL_INV(40,2018->T) PRINT(T)

END PROGRAM

{{out}}

<pre>

 

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

// Calculate the inverse of a (mod m)

// See here for eea specs:

eea t' (t - div * t') r' (r - div * r')

(m + eea 0 1 m a) % m

{{in}}

<pre>

 

=={{header|Factor}}==

{{out}}

<pre>

=={{header|Forth}}==

ANS Forth with double-number word set

: invmod { a m | v b c -- inv }

m to v

repeat b m mod dup to b 0<

if m b + else b then ;

ANS Forth version without locals

: modinv ( a m - inv)

dup 1- \ a m (m != 1)?

nip \ inv

;

<pre>

42 2017 invmod . 1969

 

=={{header|FreeBASIC}}==

' compile with: fbc -s console

 

Print : Print "hit any key to end program"

Sleep

{{out}}

<pre>a * 42 + b * 2017 = GCD(42, 2017) = 1

 

=={{header|Frink}}==

{{out}}

<pre>

 

=={{header|FunL}}==

 

def modinv( a, m ) =

if res < 0 then res + m else res

 

 

{{out}}

=={{header|Go}}==

The standard library function uses the extended Euclidean algorithm internally.

 

import (

k := new(big.Int).ModInverse(a, m)

fmt.Println(k)

{{out}}

<pre>

{{trans|Pascal}}

{{works with|PC-BASIC|any}}

10 ' Modular inverse

20 LET E% = 42

1140 LET MODINV% = D%

1150 RETURN

{{out}}

<pre>

 

=={{header|Haskell}}==

-- If there is no such x return Nothing.

modInv :: Int -> Int -> Maybe Int

 

main :: IO ()

{{out}}

<pre>Nothing

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

{{trans|C}}

a := integer(args[1]) | 42

b := integer(args[2]) | 2017

}

return if (x1 > 0) then x1 else x1+b0

 

{{out}}

Adding a coprime test:

 

 

procedure main(args)

}

return if (x1 > 0) then x1 else x1+b0

 

=={{header|IS-BASIC}}==

120 DEF MODINV(A,B)

130 LET B=ABS(B)

260 LET MODINV=T

270 END IF

 

=={{header|J}}==

'''Notes''':

 

=={{header|Java}}==

The <code>BigInteger</code> library has a method for this:

{{out}}

<pre>1969</pre>

=={{header|JavaScript}}==

Using brute force.

a %= b;

for (var x = 1; x < b; x++) {

}

}

 

=={{header|jq}}==

'''Works with gojq, the Go implementation of jq'''

 

# If $j is 0, then an error condition is raised;

# otherwise, assuming infinite-precision integer arithmetic,

# Example:

42 | modInv(2017)

{{out}}

<pre>

===Built-in===

Julia includes a built-in function for this:

 

===C translation===

The following code works on any integer type.

To maximize performance, we ensure (via a promotion rule) that the operands are the same type (and use built-ins <code>zero(T)</code> and <code>one(T)</code> for initialization of temporary variables to ensure that they remain of the same type throughout execution).

b0 = b

x0, x1 = zero(T), one(T)

x1 < 0 ? x1 + b0 : x1

end

 

{{out}}

 

=={{header|Kotlin}}==

 

import java.math.BigInteger

val m = BigInteger.valueOf(2017)

println(a.modInverse(m))

 

{{out}}

 

=={{header|MAD}}==

INTERNAL FUNCTION(AA, BB)

ENTRY TO MULINV.

SHOW.(-486,217)

SHOW.(40,2018)

{{out}}

<pre> 42, 2017: 1969

=={{header|Maple}}==

 

1/42 mod 2017;

{{out}}

<pre>

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

The built-in function <code>FindInstance</code> works well for this

 

Another way by using the built-in function <code>PowerMod</code> :

For example :

<pre>modInv[42, 2017]

 

=={{header|МК-61/52}}==

- x=0 14 С/П ИП0 1 - /-/ x<0 50

ИП0 ИП1 / [x] П4 ИП1 П3 ИП0 ^ ИП1

/ [x] ИП1 * - П1 ИП3 П0 ИП5 П3

ИП6 ИП4 ИП5 * - П5 ИП3 П6 БП 14

 

=={{header|Modula-2}}==

{{trans|C}}

FROM InOut IMPORT WriteString, WriteInt, WriteLn;

 

WriteLn;

END;

{{out}}

<pre>Modular inverse

 

=={{header|newLISP}}==

(define (modular-multiplicative-inverse a n)

(if (< n 0)

 

(println (modular-multiplicative-inverse 42 2017))

 

Output:

=={{header|Nim}}==

{{trans|C}}

var (a, b, x0) = (a0, b0, 0)

result = 1

if result < 0: result += b0

 

 

{{out}}

 

==={{trans|C}}===

let rec aux a b x0 x1 =

if a <= 1 then x1 else

in

let x = aux a b 0 1 in

 

Testing:

==={{trans|Haskell}}===

 

| 0 -> (1, 0, a)

| b ->

match gcd_ext a m with

| i, _, 1 -> mk_pos i

 

Testing:

Usage : a modulus invmod

 

// Return r = gcd(a, b) and (u, v) / r = au + bv

 

: invmod(a, modulus)

a modulus euclid 1 == ifFalse: [ drop drop null return ]

 

{{out}}

 

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

 

=={{header|Pascal}}==

// increments e step times until bal is greater than t

// repeats until bal = 1 (mod = 1) and returns count

end;

modInv := d;

 

Testing:

=={{header|Perl}}==

Various CPAN modules can do this, such as:

# or

use Math::ModInt qw/mod/; say mod(42, 2017)->inverse->residue;

use Math::GMP qw/:constant/; say 42->bmodinv(2017);

# or

or we can write our own:

my($a,$n) = @_;

my($t,$nt,$r,$nr) = (0, 1, $n, $a % $n);

}

 

'''Notes''': Special cases to watch out for include (1) where the inverse doesn't exist, such as invmod(14,28474), which should return undef or raise an exception, not return a wrong value. (2) the high bit of a or n is set, e.g. invmod(11,2**63), (3) negative first arguments, e.g. invmod(-11,23).

The modules and code above handle these cases,

=={{header|Phix}}==

{{trans|C}}

<span style="color: #008080;">function</span> <span style="color: #000000;">mul_inv</span><span style="color: #0000FF;">(</span><span style="color: #004080;">integer</span> <span style="color: #000000;">a</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span>

<span style="color: #008080;">if</span> <span style="color: #000000;">n</span><span style="color: #0000FF;"><</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">-</span><span style="color: #000000;">n</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>

<span style="color: #0000FF;">?</span><span style="color: #000000;">mul_inv</span><span style="color: #0000FF;">(-</span><span style="color: #000000;">486</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">217</span><span style="color: #0000FF;">)</span>

<span style="color: #0000FF;">?</span><span style="color: #000000;">mul_inv</span><span style="color: #0000FF;">(</span><span style="color: #000000;">40</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">2018</span><span style="color: #0000FF;">)</span>

{{out}}

<pre>

=={{header|PHP}}==

'''Algorithm Implementation'''

function invmod($a,$n){

if ($n < 0) $n = -$n;

}

printf("%d\n", invmod(42, 2017));

{{Out}}

<pre>1969</pre>

=={{header|PicoLisp}}==

{{trans|C}}

(let (B0 B X0 0 X1 1 Q 0 T1 0)

(while (< 1 A)

(modinv 42 2017) )

 

 

=={{header|PL/I}}==

{{trans|REXX}}

/*--------------------------------------------------------------------

* 13.07.2015 Walter Pachl

Return(d);

End;

{{out}}

<pre>modular inverse of 42 by 2017 ---> 1969</pre>

 

=={{header|PowerShell}}==

if ([int]$n -lt 0) {$n = -$n}

if ([int]$a -lt 0) {$a = $n - ((-$a) % $n)}

}

 

{{Out}}

<pre>PS> .\INVMOD.PS1

 

=={{header|Prolog}}==

egcd(_, 0, 1, 0) :- !.

egcd(A, B, X, Y) :-

A*X + B*Y =:= 1,

N is X mod B.

{{Out}}

<pre>

=={{header|PureBasic}}==

Using brute force.

Declare main()

Declare.i mi(a.i, b.i)

If x > y - 1 : x = -1 : EndIf

ProcedureReturn x

{{out}}

<pre> MODULAR-INVERSE( 42, 2017) = 1969

===Iteration and error-handling===

Implementation of this [http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm#Iterative_method_2 pseudocode] with [https://en.wikibooks.org/wiki/Algorithm_Implementation/Mathematics/Extended_Euclidean_algorithm#Modular_inverse this].

lastremainder, remainder = abs(aa), abs(bb)

x, lastx, y, lasty = 0, 1, 1, 0

>>> modinv(42, 2017)

1969

 

===Recursion and an option type===

Or, using functional composition as an alternative to iterative mutation, and wrapping the resulting value in an option type, to allow for the expression of computations which establish the '''absence''' of a modular inverse:

 

from itertools import (chain)

 

 

# MAIN ---

{{Out}}

<pre>

{{trans|Forth}}

 

[ tuck 1 0

[ swap temp put

nip ] is modinv ( n n --> n )

 

 

{{out}}

 

=={{header|Racket}}==

(require math)

(modular-inverse 42 2017)

{{out}}

1969

 

=={{header|Raku}}==

(formerly Perl 6)

my ($c, $d, $uc, $vc, $ud, $vd) = ($n % $modulo, $modulo, 1, 0, 0, 1);

my $q;

}

 

 

=={{header|REXX}}==

parse arg x y . /*obtain two integers from the C.L. */

if x=='' | x=="," then x= 42 /*Not specified? Then use the default.*/

 

if $<0 then $= $ + ob /*Negative? Then add the original B. */

{{out|output|text=&nbsp; when using the default inputs of: &nbsp; &nbsp; <tt> 42 &nbsp; 2017 </tt>}}

<pre>

 

=={{header|Ring}}==

see "42 %! 2017 = " + multInv(42, 2017) + nl

 

if multInv < 0 multInv = multInv + b0 ok

return multInv

Output:

<pre>

 

=={{header|Ruby}}==

def extended_gcd(a, b)

last_remainder, remainder = a.abs, b.abs

end

x % et

<pre>

> invmod(42,2017)

 

Simplified equivalent implementation

def modinv(a, m) # compute a^-1 mod m if possible

raise "NO INVERSE - #{a} and #{m} not coprime" unless a.gcd(m) == 1

inv

end

<pre>

> modinv(42,2017)

 

=={{header|Run BASIC}}==

end

 

if multInv < 0 then multInv = multInv + b0

[endFun]

 

{{out}}

 

=={{header|Rust}}==

let mut mn = (module, a);

let mut xy = (0, 1);

fn main() {

println!("{}", mod_inv(42, 2017))

 

{{out}}

 

Alternative implementation

fn modinv(a0: isize, m0: isize) -> isize {

if m0 == 1 { return 1 }

fn main() {

println!("{}", modinv(42, 2017))

 

{{out}}

=={{header|Scala}}==

Based on the ''Handbook of Applied Cryptography'', Chapter 2. See http://cacr.uwaterloo.ca/hac/ .

def gcdExt(u: Int, v: Int): (Int, Int, Int) = {

@tailrec

val (i, j, g) = gcdExt(a, m)

if (g == 1) Option(if (i < 0) i + m else i) else Option.empty

 

Translated from C++ (on this page)

def modInv(a: Int, m: Int, x:Int = 1, y:Int = 0) : Int = if (m == 0) x else modInv(m, a%m, y, x - y*(a/m))

 

{{out}}

If a and b are not coprime (gcd(a, b) <> 1) the exception RANGE_ERROR is raised.

 

in var bigInteger: b) is func

result

raise RANGE_ERROR;

end if;

 

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

=={{header|Sidef}}==

Built-in:

 

Algorithm implementation:

var (t, nt, r, nr) = (0, 1, n, a % n)

while (nr != 0) {

}

 

{{out}}

<pre>

=={{header|Swift}}==

 

@inlinable

public func modInv(_ mod: Self) -> Self {

}

 

 

{{out}}

=={{header|Tcl}}==

{{trans|Haskell}}

if {$b == 0} {

return [list 1 0 $a]

while {$i < 0} {incr i $m}

return $i

Demonstrating

catch {

puts "2 %! 4 = [modInv 2 4]"

{{out}}

<pre>

=={{header|Tiny BASIC}}==

2017 causes integer overflow, so I'll do the inverse of 42 modulo 331 instead.

PRINT "Modular inverse."

PRINT "What is the modulus?"

LET B = B - M

GOTO 30

{{out}}

<pre>Modular inverse.

Another version:

{{trans|GW-BASIC}}

REM Modular inverse

LET E=42

130 LET M=D

RETURN

{{out}}

<pre>

 

=={{header|tsql}}==

AS (

SELECT

)

SELECT *

 

== {{header|TypeScript}} ==

{{trans|Pascal}}

// Modular inverse

 

 

console.log(`${modInv(42, 2017)}`); // 1969

{{out}}

<pre>

=={{header|uBasic/4tH}}==

{{trans|C}}

End

 

 

If g@ < 0 Then g@ = g@ + c@

{{trans|Perl}}

Print FUNC(_mul_inv(40, 1))

Print FUNC(_mul_inv(52, -217))

If (e@ > 1) Return (-1) ' No inverse'

If (c@ < 0) c@ = c@ + b@

{{out}}

<pre>1969

{{works with|Korn Shell}}

{{works with|Zsh}}

typeset -i a=$1 n=$2

if (( n < 0 )); then (( n = -n )); fi

}

 

 

{{Out}}

 

=={{header|VBA}}==

Private Function mul_inv(a As Long, n As Long) As Variant

If n < 0 Then n = -n

Debug.Print mul_inv(-486, 217)

Debug.Print mul_inv(40, 2018)

<pre> 1969

0

=={{header|Wren}}==

{{libheader|Wren-big}}

 

var a = BigInt.new(42)

var b = BigInt.new(2017)

 

{{out}}

 

=={{header|XPL0}}==

int X;

def A=42, M=2017;

if rem(A*X/M) = 1 then [IntOut(0, X); exit];

Text(0, "Does not exist");

{{out}}

<pre>

=={{header|zkl}}==

{{trans|Haskell}}

if(b==0) return(1,0,a);

q,r:=a.divr(b); s,t,g:=gcdExt(b,r); return(t,s-q*t,g);

}

divr(a,b) is [integer] (a/b,remainder)

{{out}}