Modular inverse: Difference between revisions
m
→{{header|Wren}}: Minor tidy
m (→{{header|Wren}}: Minor tidy) |
|||
| (5 intermediate revisions by 3 users not shown) | |||
Line 2,064:
<pre>ModularInverse[42, 2017]
1969</pre>
=={{header|Maxima}}==
Using built-in function inv_mod
<syntaxhighlight lang="maxima">
inv_mod(42,2017);
</syntaxhighlight>
{{out}}
<pre>
1969
</pre>
=={{header|Mercury}}==
Line 2,791 ⟶ 2,801:
=={{header|Python}}==
===Builtin function===
Since python3.8, builtin function "pow" can be used directly to compute modular inverses by specifying an exponent of -1:
<syntaxhighlight lang="python">>>> pow(42, -1, 2017)
1969
</syntaxhighlight>
===Iteration and error-handling===
Line 2,936 ⟶ 2,952:
<pre>1969</pre>
===Using Extended Euclidean Algorithm===
Handles negative args. Returns -1 for non-coprime args.
<syntaxhighlight lang="quackery"> [ dup 0 = iff
[ 2drop 1 0 ]
done
dup unrot /mod
dip swap recurse
tuck 2swap *
dip swap - ] is egcd ( n n --> n n )
[ dup 0 < if negate
over 0 < if
[ swap negate
over tuck mod
- swap ]
dup rot 2dup egcd
2swap 2over rot *
unrot * + 1 != iff
[ drop 2drop -1 ]
done
nip swap mod ] is modinv ( n n --> n )
say " 42 2017 modinv --> " 42 2017 modinv echo cr ( --> 1969 )
say " 40 1 modinv --> " 40 1 modinv echo cr ( --> 0 )
say " 52 -217 modinv --> " 52 -217 modinv echo cr ( --> 96 )
say "-486 217 modinv --> " -486 217 modinv echo cr ( --> 121 )
say " 40 2018 modinv --> " 40 2018 modinv echo cr ( --> -1 )</syntaxhighlight>
{{out}}
<pre> 42 2017 modinv --> 1969
40 1 modinv --> 0
52 -217 modinv --> 96
-486 217 modinv --> 121
40 2018 modinv --> -1
</pre>
=={{header|Racket}}==
Line 3,635 ⟶ 3,690:
=={{header|Wren}}==
{{libheader|Wren-big}}
<syntaxhighlight lang="
var a = BigInt.new(42)
| |||