0

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;
    }
1
  • Please provide some sample input, the desired output, and the actual output.
    – agc
    Commented May 15, 2018 at 4:35

1 Answer 1

4

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.)

2
  • 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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .