How to resolve the algorithm Modular exponentiation step by step in the ObjectIcon programming language

Published on 12 May 2024 09:40 PM

How to resolve the algorithm Modular exponentiation step by step in the ObjectIcon programming language

Table of Contents

Problem Statement

Find the last   40   decimal digits of

a

b

{\displaystyle a^{b}}

,   where

A computer is too slow to find the entire value of

a

b

{\displaystyle a^{b}}

. Instead, the program must use a fast algorithm for modular exponentiation:

a

b

mod

m

{\displaystyle a^{b}\mod m}

. The algorithm must work for any integers

a , b , m

{\displaystyle a,b,m}

,     where

b ≥ 0

{\displaystyle b\geq 0}

and

m

0

{\displaystyle m>0}

.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Modular exponentiation step by step in the ObjectIcon programming language

Source code in the objecticon programming language

# -*- ObjectIcon -*-
#
# This program is close to being an exact copy of the Icon.
#

import io # <-- Object Icon requires this for I/O.

procedure main()
  local a, b # <-- Object Icon forces you to declare your variables.

  a := 2988348162058574136915891421498819466320163312926952423791023078876139
  b := 2351399303373464486466122544523690094744975233415544072992656881240319 

  # You could leave out the "io." in the call to "write" below,
  # because there is some "compatibility with regular Icon" support in
  # the io package.
  io.write("last 40 digits = ", mod_power(a,b,(10^40)))
end

procedure mod_power(base, exponent, modulus)
  local result

  result := 1
  while exponent > 0 do
  {
    if exponent % 2 = 1 then
      result := (result * base) % modulus
    exponent /:= 2
    base := base ^ 2 % modulus
  }  
  return result
end

  

You may also check:How to resolve the algorithm Command-line arguments step by step in the Pure programming language
You may also check:How to resolve the algorithm Factorial step by step in the Wrapl programming language
You may also check:How to resolve the algorithm Comments step by step in the Logo programming language
You may also check:How to resolve the algorithm Hello world/Text step by step in the Nyquist programming language
You may also check:How to resolve the algorithm Hello world/Text step by step in the BlitzMax programming language