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

Published on 12 May 2024 09:40 PM
#8th

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

Source code in the 8th programming language

\ 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

You may also check:How to resolve the algorithm MAC vendor lookup step by step in the Go programming language
You may also check:How to resolve the algorithm Sum of a series step by step in the Icon and Unicon programming language
You may also check:How to resolve the algorithm Sorting Algorithms/Circle Sort step by step in the ZX Spectrum Basic programming language
You may also check:How to resolve the algorithm Modular inverse step by step in the Craft Basic programming language
You may also check:How to resolve the algorithm Maximum triangle path sum step by step in the VBScript programming language