user
This task has been flagged for clarification. Code on this page in its current state may be flagged incorrect once this task has been clarified. See this page's Talk page for discussion.

Implement the Montgomery reduction algorithm, as explained in "Handbook of Applied Cryptography, Section 14.3.2, page 600. Montgomery reduction calculates 

T

R

−
1

m
o
d
m
{\displaystyle {\displaystyle TR^{-1}\mathrm {mod} m}}
, without having to divide by 

m
{\displaystyle {\displaystyle m}}
.

* Let 

  M
  {\displaystyle {\displaystyle M}}
   be a positive integer, and 

  R
  {\displaystyle {\displaystyle R}}
   and 

  T
  {\displaystyle {\displaystyle T}}
   integers such that 

  R
  >
  m
  {\displaystyle {\displaystyle R>m}}
  , 

  g
  c
  d
  (
  m
  ,
  R
  )
  =
  1
  {\displaystyle {\displaystyle \mathrm {gcd} (m,R)=1}}
  , and 

  0
  ≤
  T
  <
  m
  R
  {\displaystyle {\displaystyle 0\leq T<mR}}
  .
* R
  {\displaystyle {\displaystyle R}}
   is usually chosen as 

  b

  n
  {\displaystyle {\displaystyle b^{n}}}
  , where 

  b
  {\displaystyle {\displaystyle b}}
   = base (radix) in which the numbers in the calculation as represented in (so 

  b
  =
  10
  {\displaystyle {\displaystyle b=10}}
   in ‘normal’ paper arithmetic, 

  b
  =
  2
  {\displaystyle {\displaystyle b=2}}
   for computer implementations) and 

  n
  {\displaystyle {\displaystyle n}}
   = number of digits in base 

  m
  {\displaystyle {\displaystyle m}}
* The numbers 

  m
  {\displaystyle {\displaystyle m}}
   (

  n
  {\displaystyle {\displaystyle n}}
   digits long), 

  T
  {\displaystyle {\displaystyle T}}
   (

  2
  n
  {\displaystyle {\displaystyle 2n}}
   digits long), 

  R
  {\displaystyle {\displaystyle R}}
  , 

  b
  {\displaystyle {\displaystyle b}}
  , 

  n
  {\displaystyle {\displaystyle n}}
   are known entities, a number 

  m
  ′
  {\displaystyle {\displaystyle m'}}
   (often represented as `m_dash` in code) = 

  −

  m

  −
  1

  m
  o
  d
  b
  {\displaystyle {\displaystyle -m^{-1}\mathrm {mod} b}}
   is precomputed.

See the Handbook of Applied Cryptography for brief introduction to theory and numerical example in radix 10. Individual chapters of the book can be viewed online as provided by the authors. The said algorithm can be found at [1] at page 600 (page 11 of pdf file)

Algorithm:

```
A ← T (temporary variable)
For i from 0 to (n-1) do the following:
   ui ← ai* m' mod b      // ai is the ith digit of A, ui is a single digit number in radix b
   A ← A + ui*m*bi
A ← A/bn
if A >= m,
   A ← A - m
Return (A)

```
assistant
(formerly Perl 6)

**Works with**: Rakudo version 2018.03

**Translation of**: Sidef

```
sub montgomery-reduce($m, $a is copy) {
    for 0..$m.msb {
        $a += $m if $a +& 1;
        $a +>= 1
    }
    $a % $m
}

my $m  = 750791094644726559640638407699;
my $t1 = 323165824550862327179367294465482435542970161392400401329100;

my $r1 = 440160025148131680164261562101;
my $r2 = 435362628198191204145287283255;

my $x1 = 540019781128412936473322405310;
my $x2 = 515692107665463680305819378593;

say "Original x1:       ", $x1;
say "Recovered from r1: ", montgomery-reduce($m, $r1);
say "Original x2:       ", $x2;
say "Recovered from r2: ", montgomery-reduce($m, $r2);

print "\nMontgomery  computation x1**x2 mod m: ";
my $prod = montgomery-reduce($m, $t1/$x1);
my $base = montgomery-reduce($m, $t1);

for $x2, {$_ +> 1} ... 0 -> $exponent {
    $prod = montgomery-reduce($m, $prod * $base) if $exponent +& 1;
    $base = montgomery-reduce($m, $base * $base);
}

say montgomery-reduce($m, $prod);
say "Built-in op computation x1**x2 mod m: ", $x1.expmod($x2, $m);

```

Output:

```
Original x1:       540019781128412936473322405310
Recovered from r1: 540019781128412936473322405310
Original x2:       515692107665463680305819378593
Recovered from r2: 515692107665463680305819378593

Montgomery  computation x1**x2 mod m: 151232511393500655853002423778
Built-in op computation x1**x2 mod m: 151232511393500655853002423778

```