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

Published on 12 May 2024 09:40 PM
#Perl

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

Source code in the perl programming language

use bigint; say 42->bmodinv(2017);
# or
use Math::ModInt qw/mod/;  say mod(42, 2017)->inverse->residue;
# or
use Math::Pari qw/PARI lift/; say lift PARI "Mod(1/42,2017)";
# or
use Math::GMP qw/:constant/; say 42->bmodinv(2017);
# or
use ntheory qw/invmod/; say invmod(42, 2017);


sub invmod {
  my($a,$n) = @_;
  my($t,$nt,$r,$nr) = (0, 1, $n, $a % $n);
  while ($nr != 0) {
    # Use this instead of int($r/$nr) to get exact unsigned integer answers
    my $quot = int( ($r - ($r % $nr)) / $nr );
    ($nt,$t) = ($t-$quot*$nt,$nt);
    ($nr,$r) = ($r-$quot*$nr,$nr);
  }
  return if $r > 1;
  $t += $n if $t < 0;
  $t;
}

say invmod(42,2017);

You may also check:How to resolve the algorithm Percolation/Mean run density step by step in the Julia programming language
You may also check:How to resolve the algorithm Keyboard input/Keypress check step by step in the MiniScript programming language
You may also check:How to resolve the algorithm S-expressions step by step in the Julia programming language
You may also check:How to resolve the algorithm Arena storage pool step by step in the FreeBASIC programming language
You may also check:How to resolve the algorithm Sequence of non-squares step by step in the Erlang programming language