Inverse modulo operations in bash-CodePudding

I am trying to write a bash script that will be able to do inverse modulo operations. Currently the program can do regular mod calculations but trying to do inverse modulo operations leaves me with wrong answers (either prints 0's or wrong answers). Is it even possible to do inverse calculations, if so what would be the formula?

Expected Result:

28 14 22 30 18 32 30 12 25 37 8 31 18 4 37 3 33 35 27 2 4 3 28

Gotten Results:

-23 -4 -29 -27 -17 -10 -27 -25 -24 -11 -37 -5 -17 -32 -11 -15 -6 -35 -39 -22

#!/bin/bash
flag_enc=(268 413 110 190 426 419 108 229 310 379 323 373 385 236 92 96 169 321 284 185 154 137 186) #inputs

for i in "${flag_enc[@]}"
do
mod=$((1 / $i))      # input^(-1)
modus=$(($mod % 41)) #mod41 calculation
echo "$modus"
done

Oguz Ismail gave the right mathematical expression for calculating inverse mod in bash. I am attaching the modified the script bellow:

flag_enc=(268 413 110 190 426 419 108 229 310 379 323 373 385 236 92 96 169 321 284 185 154 137 186)
m=41

for i in "${flag_enc[@]}"
do
    for ((x = 1; x < m; x  )); do
    if ((($i % m) * (x % m) % m == 1)); then
      echo $x     
fi
done
done

CodePudding user response：

I don't know if your algorithm is correct or not, but bash doesn't support floating point arithmetic intrinsically.

So either use bc, or define a function like below

mmi() {
  a=$1
  m=$2

  for ((x = 1; x < m; x  )); do
    if (((a % m) * (x % m) % m == 1)); then
      echo $x
      return 0
    fi
  done

  return 1
}

and use it like so:

$ mmi 268 41
28

CodePudding user response：

Better use a dedicated tool or programming language. Example with the gmpy2 module of python (without error handling, this is left as an exercise):

for i in "${flag_enc[@]}"; do
  mod=$(printf 'import gmpy2\nprint(int(gmpy2.invert(%d, %d)))\n' "$i" "41" | python)
  echo "$mod"
done