25 lines
736 B
Text
25 lines
736 B
Text
[ 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 )
|