Modular inverse: Difference between revisions
(+J) |
|||
Line 75: | Line 75: | ||
1969 |
1969 |
||
>>> </lang> |
>>> </lang> |
||
=={{header|Run BASIC}}== |
|||
<lang runbasic>print multInv(42, 2017) |
|||
end |
|||
function multInv(a,b) |
|||
b0 = b |
|||
multInv = 1 |
|||
if b = 1 then goto [endFun] |
|||
while a > 1 |
|||
q = a / b |
|||
t = b |
|||
b = a mod b |
|||
a = t |
|||
t = x0 |
|||
x0 = multInv - q * x0 |
|||
multInv = int(t) |
|||
wend |
|||
if multInv < 0 then multInv = multInv + b0 |
|||
[endFun] |
|||
end function</lang>1969 |
Revision as of 16:36, 1 December 2012
From Wikipedia:
- In modular arithmetic, the modular multiplicative inverse of an integer a modulo m is an integer x such that
Or in other words, such that
It can be shown that such an inverse exists if and only if a and m are coprime, but we will ignore this for this task.
Either by implementing the algorithm, by using a dedicated library or by using a builtin function in your language, compute the modular inverse of 42 modulo 2017.
C
<lang c>#include <stdio.h>
int mul_inv(int a, int b) { int b0 = b, t, q; int x0 = 0, x1 = 1; if (b == 1) return 1; while (a > 1) { q = a / b; t = b, b = a % b, a = t; t = x0, x0 = x1 - q * x0, x1 = t; } if (x1 < 0) x1 += b0; return x1; }
int main(void) { printf("%d\n", mul_inv(42, 2017)); return 0; }</lang>
J
Solution:<lang j> modInv =: dyad def 'x y&|@^ <: 5 p: y'"0</lang> Example:<lang j> 42 modInv 2017 1969</lang> Notes: Calculates the modular inverse as a^( totient(m) - 1 ) mod m. Note that J has a fast implementation of modular exponentiation (which avoids the exponentiation altogether), invoked with the form m&|@^ (hence, we use explicitly-named arguments for this entry, as opposed to the "variable free" tacit style).
Java
The BigInteger
library has a method for this:
<lang java>System.out.println(BigInteger.valueOf(42).modInverse(BigInteger.valueOf(2017)));</lang>
- Output:
1969
Perl
The modular inverse is not a perl builtin but there is a CPAN module who does the job.
<lang perl>use Math::ModInt qw(mod); print mod(42, 2017)->inverse</lang>
- Output:
mod(1969, 2017)
Python
Implementation of this pseudocode with this. <lang python>>>> def extended_gcd(aa, bb):
a, b = abs(aa), abs(bb) x, lastx, y, lasty = 0, 1, 1, 0 while b: a, (quotient, b) = b, divmod(a, b) x, lastx = lastx - quotient*x, x y, lasty = lasty - quotient*y, y return a, lastx * (-1 if aa < 0 else 1), lasty * (-1 if bb < 0 else 1)
>>> def modinv(a, m): g, x, y = extended_gcd(a, m) if g != 1: raise ValueError return x % m
>>> modinv(42, 2017) 1969 >>> </lang>
Run BASIC
<lang runbasic>print multInv(42, 2017) end
function multInv(a,b) b0 = b multInv = 1 if b = 1 then goto [endFun] while a > 1 q = a / b t = b b = a mod b a = t t = x0 x0 = multInv - q * x0 multInv = int(t) wend if multInv < 0 then multInv = multInv + b0 [endFun] end function</lang>1969