Inverse modulo operations in bash

Question

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

Can you share more details about the inputs and the expected outputs? What do you mean by "inverse modulo"? — Nico Haase, Oct 11 '22 at 09:05
@NicoHaase What I mean by "inverse modulo" is inverse modular multiplicative. The inputs are in the array list called "flag_enc". With the current script my answers are zeroes or just wrong ones. Example: 268 mod 41 = 22; Inverse modulo - 268 ^ -1 mod41 = 28, the answer that I get is "-23" — justcain, Oct 11 '22 at 09:19
This seems like a math question rather than a programming question. https://math.stackexchange.com/questions/746028/inverse-modulo-function has some sort of solution. Implementing it in Bash seems like an odd choice. — tripleee, Oct 11 '22 at 09:35
Please add all clarification to your question by editing it. What **exactly** did you try to resolve the problem? — Nico Haase, Oct 11 '22 at 09:37
You can't do floating-point arithmetic in Bash. Easiest imho is to use zsh. See https://stackoverflow.com/questions/12722095/how-do-i-use-floating-point-arithmetic-in-bash. Also remove the extra first for loop `for ((i = 0; i < 22 ; i++)); do`. I have no idea what that's for. — Alex, Oct 11 '22 at 09:37
@tripleee It is a programming math questionsInverse modulo functions are a bit different than modulo operations. The inverse mod mathematical equation can be written as follows: a * x = 1 mod. I do agree that bash is a weird choice but why not. — justcain, Oct 11 '22 at 09:42
There's also the problem that any 0,... decimal modulo an integer will give the 0,... decimal itself. Something is def off with these calculations. Consider the below run in zsh: `~/ % echo $(( 1.0 / 268)) 0.0037313432835820895 ~/ % echo $(( 0.0037313432835820895 % 41 )) 0.0037313432835820895` — Alex, Oct 11 '22 at 09:49
Thanks @Alex, probably because bash does not do proper floating-point arithmetic I do not get proper answers also "bc -l" does not work. I guess my best bet is to write a script w/ python. — justcain, Oct 11 '22 at 10:03
"Why can't I use floating-point arithmetic in Bash" makes this a duplicate of https://stackoverflow.com/questions/12722095/how-do-i-use-floating-point-arithmetic-in-bash — tripleee, Oct 13 '22 at 05:10

score 1 · Accepted Answer · answered Oct 11 '22 at 09:57

1

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

answered Oct 11 '22 at 09:57

oguz ismail

1
16
47
69

Thanks! This will work perfectly. I did not know how to write the mathematical expression correctly and will keep in mind that bash does not do floating point arithmetics – justcain Oct 11 '22 at 10:24

score 1 · Answer 2 · answered Oct 11 '22 at 11:23

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

Inverse modulo operations in bash

2 Answers2