# How to script an an exponential function that decrements the value of the exponent every iteration so that the exponent does not grow?

New to Linux and having problems getting this script to run.

Been working on something to take large numbers and use the remainder (modulus) to store the result ( to save memory ).

Using the bash shell I am trying to compute 78390^91025(mod 180577) So using the base 78290 the power of 91025 and applying the modulus of 180577.

I wish to obtain the following logic: y=base for i = 1 to the exponent-1 y := (y*base) mod 'modulus' next i print y

In doing this I hope to save memory and storage while still obtaining the correct result.

I've been tinkering around with the code and now cannot get it to run.. Where am I messing up?

``````#!/bin/bash

#   k^x (mod n)
#   with k=78390, x=91025, n=180577 ?
#   Script runs but no output,
#   pretty sure it is close

powmod() {
let "a=1"
let "k=\$1"
let "x=\$2"
let "n=\$3"
while (( x )); do
if (( x % 2 )); then
(( a = a*k % n ))
(( x = x-1 ))
fi
(( k = k*k % n ))
(( x = x/2 ))
done
echo \$a;
}
``````
• Please provide some sample input, the desired output, and the actual output.
– agc
Commented May 15, 2018 at 4:35

Okay, you want to calculate `k^x (mod n)` with `k=78390`, `x=91025`, `n=180577`. The simplest way is indeed to repeatedly multiply the base (`k`) to an accumulator, as your pseudo-code presents. Here's a Bash function to do that:

``````powmod() {
local a=1 k=\$1 x=\$2 n=\$3;
for (( ; x; x-- )) {
(( a=a*k % n ));
};
echo \$a;
}
``````

Now, `powmod 78390 91025 180577` prints `125`. (The result agrees with what Wolfram Alpha gives.)

Note that you need to initialize `a` to one, not to the base, since an exponent of zero should return one, not the base (`k^0 = 1`, regardless of `k`).

Alternative implementation in `bc`:

``````k=78390
x=91025
n=180577
a=1
while (x > 0) {
a=a*k % n
x=x-1
}
a
``````

Not surprisingly, `bc` is faster than Bash.

Instead of the simple loop, a smarter way would be to use the square-and-multiply algorithm. It's significantly faster, since it only uses `log2(x)` operations, rather than `x` as the above does.

In Bash:

``````powmod2() {
local a=1 k=\$1 x=\$2 n=\$3;
while (( x )); do
if (( x % 2 )); then
(( a = a*k % n ))
(( x = x-1 ))
fi
(( k = k*k % n ))
(( x = x/2 ))
done
echo \$a;
}
``````

That's rather fast with numbers of this size, but note that you get silent failures if the temporary values (`a*k` or `k*k`, before the modulo) get larger than Bash can handle. (The numbers here are fine, since `180577*180577` fits in 64 bits.)

I can't come up with a trivial way of detecting the overflow, without hard-coding a limit, so you might want to use `bc` in any case:

``````k=78390
i=91025
n=180577
a=1
while (i > 0) {
if (i % 2) {
a=a*k % n
i=i-1
}
k=k*k % n
i=i/2
}
a
``````

(Sticking the call to `bc` in a shell function should be trivial.)

• That is great, thank you for taking the time to explain it to me. Commented May 16, 2018 at 2:46
• I try to run it from the terminal as an executable and it runs but does not give me any feedback? Commented May 16, 2018 at 2:47