mod-inv ( x n -- y ) (original) (raw)

mod-inv ( x n -- y )
Factor handbook » The language » Numbers » Mathematical functions » Integer functions

Prev: ^mod ( x y n -- z )
Next: power-of-2? ( n -- ? )

Vocabulary
math.functions

Inputs

x an integer
n an integer

Outputs

y an integer

Word description
Outputs a positive integer y such that x*y = 1 (mod n).

Errors
Throws an error if x is not invertible modulo n.

Examples

USING: math.functions prettyprint ; 173 1119 mod-inv .
815

USING: math prettyprint ; 173 815 * 1119 mod .
1

Definition

USING: kernel math math.functions.private ;

IN: math.functions

: mod-inv ( x n -- y )
[ gcd 1 = ] 1check
[ >positive-mod ] [ non-trivial-divisor ] if ; foldable
flushable