How to resolve the algorithm Modular inverse step by step in the Common Lisp programming language

Published on 12 May 2024 09:40 PM

How to resolve the algorithm Modular inverse step by step in the Common Lisp programming language

Table of Contents

Problem Statement

From Wikipedia: In modular arithmetic,   the modular multiplicative inverse of an integer   a   modulo   m   is an integer   x   such that Or in other words, such that: It can be shown that such an inverse exists   if and only if   a   and   m   are coprime,   but we will ignore this for this task.

Either by implementing the algorithm, by using a dedicated library or by using a built-in function in your language,   compute the modular inverse of   42 modulo 2017.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Modular inverse step by step in the Common Lisp programming language

Source code in the common programming language

;;
;; Calculates the GCD of a and b based on the Extended Euclidean Algorithm. The function also returns
;; the Bézout coefficients s and t, such that gcd(a, b) = as + bt.
;;
;; The algorithm is described on page http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm#Iterative_method_2
;;
(defun egcd (a b)
  (do ((r (cons b a) (cons (- (cdr r) (* (car r) q)) (car r))) ; (r+1 r) i.e. the latest is first.
       (s (cons 0 1) (cons (- (cdr s) (* (car s) q)) (car s))) ; (s+1 s)
       (u (cons 1 0) (cons (- (cdr u) (* (car u) q)) (car u))) ; (t+1 t)
       (q nil))
      ((zerop (car r)) (values (cdr r) (cdr s) (cdr u)))       ; exit when r+1 = 0 and return r s t
    (setq q (floor (/ (cdr r) (car r))))))                     ; inside loop; calculate the q

;;
;; Calculates the inverse module for a = 1 (mod m). 
;;
;; Note: The inverse is only defined when a and m are coprimes, i.e. gcd(a, m) = 1.”
;;
(defun invmod (a m)
  (multiple-value-bind (r s k) (egcd a m)
    (unless (= 1 r) (error "invmod: Values ~a and ~a are not coprimes." a m))  
     s))


  

You may also check:How to resolve the algorithm Active Directory/Connect step by step in the Ruby programming language
You may also check:How to resolve the algorithm One-dimensional cellular automata step by step in the Fantom programming language
You may also check:How to resolve the algorithm N'th step by step in the Prolog programming language
You may also check:How to resolve the algorithm Modular arithmetic step by step in the D programming language
You may also check:How to resolve the algorithm Superpermutation minimisation step by step in the PureBasic programming language