Modular inverse: Difference between revisions
Content added Content deleted
imported>Maxima enthusiast No edit summary |
(→{{header|Quackery}}: Added second method) |
||
Line 2,946: | Line 2,946: | ||
<pre>1969</pre> |
<pre>1969</pre> |
||
Handles negative args. Returns -1 for non-coprime args. |
|||
===Using Extended Euclidean Algorithm=== |
|||
<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}}== |
=={{header|Racket}}== |