123456789101112131415161718192021222324252627282930 |
- #!/usr/bin/ruby
- # Algorithm for computing the modular multiplicative inverse: 1/a mod n, with gcd(a, n) = 1.
- # Algorithm presented in the book:
- #
- # Modern Computer Arithmetic
- # - by Richard P. Brent and Paul Zimmermann
- #
- func modular_inverse (a, n) {
- var (u, w) = (1, 0)
- var (q, r) = (0, 0)
- var c = n
- while (c != 0) {
- (q, r) = divmod(a, c)
- (a, c) = (c, r)
- (u, w) = (w, u - q*w)
- }
- u += n if (u < 0)
- return u
- }
- say modular_inverse(42, 2017) #=> 1969
|