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

Published on 12 May 2024 09:40 PM
#Erre

How to resolve the algorithm Modular inverse step by step in the ERRE 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 ERRE programming language

Source code in the erre programming language

PROGRAM MOD_INV

!$INTEGER

PROCEDURE MUL_INV(A,B->T)
  LOCAL NT,R,NR,Q,TMP
  IF B<0 THEN B=-B
  IF A<0 THEN A=B-(-A MOD B)
  T=0  NT=1  R=B  NR=A MOD B
  WHILE NR<>0 DO
      Q=R DIV NR
      TMP=NT  NT=T-Q*NT  T=TMP
      TMP=NR  NR=R-Q*NR  R=TMP
  END WHILE
  IF (R>1) THEN T=-1 EXIT PROCEDURE  ! NO INVERSE
  IF (T<0) THEN T+=B
END PROCEDURE


BEGIN
     MUL_INV(42,2017->T) PRINT(T)
     MUL_INV(40,1->T) PRINT(T)
     MUL_INV(52,-217->T) PRINT(T)    ! pari semantics for negative modulus
     MUL_INV(-486,217->T)  PRINT(T)
     MUL_INV(40,2018->T) PRINT(T)
END PROGRAM

You may also check:How to resolve the algorithm Delete a file step by step in the NewLISP programming language
You may also check:How to resolve the algorithm Fibonacci n-step number sequences step by step in the AppleScript programming language
You may also check:How to resolve the algorithm Arrays step by step in the LSL programming language
You may also check:How to resolve the algorithm Constrained random points on a circle step by step in the Frink programming language
You may also check:How to resolve the algorithm Date manipulation step by step in the Maple programming language