25 lines
518 B
Plaintext
25 lines
518 B
Plaintext
\ return "extended gcd" of a and b; The result satisfies the equation:
|
|
\ a*x + b*y = gcd(a,b)
|
|
: n:xgcd \ a b -- gcd x y
|
|
dup 0 n:= if
|
|
1 swap \ -- a 1 0
|
|
else
|
|
tuck n:/mod
|
|
-rot recurse
|
|
tuck 4 roll
|
|
n:* n:neg n:+
|
|
then ;
|
|
|
|
\ Return modular inverse of n modulo mod, or null if it doesn't exist (n and mod
|
|
\ not coprime):
|
|
: n:invmod \ n mod -- invmod
|
|
dup >r
|
|
n:xgcd rot 1 n:= not if
|
|
2drop null
|
|
else
|
|
drop dup 0 n:< if r@ n:+ then
|
|
then
|
|
rdrop ;
|
|
|
|
42 2017 n:invmod . cr bye
|