0

I am writing a (what I thought) was a simple program implementing the affine cipher and have come across an issue in that I am not getting expected results from the modulo in C89.

int main()
{
    foo(10);
    return 0;
}

int foo(int enc)
{
    int a = 5, b = 22, inv_a = 77, result;
    result = (inv_a * (enc - b)) % 128;
    printf("result = %d = %c\n", result, result);
    return result;
}

The result of the above is -28 (undefined behavior?)

Meanwhile, the same function in python:

def foo(enc):
    a = 5
    b = 22
    inv_a = 77
    result = (inv_a * (enc - b)) % 128
    print(result)

foo(10)

returns my expected result of 100. During the debugging process I found the results are the same up to the modulo is used. What is happening in the C modulo I am unaware of?

Kevin DeCara
  • 7
  • 2
  • It's not undefined - it's just defined differently than you expected. (Notice that 100 and -28 are congruent mod 128, so in a certain mathematical sense, both are "correct".) – Nate Eldredge Nov 17 '21 at 18:36
  • "C modulo" --> C lacks a Euclidean modulo: [What's the difference between “mod” and “remainder”?](https://stackoverflow.com/a/20638659/2410359) may be useful for understanding C. – chux - Reinstate Monica Nov 17 '21 at 20:22

1 Answers1

0

The % operator in C is does not actually perform modulo, but the remainder of division. The latter allows for negative values.

Specifically, from section 6.5.5p6 of the C standard:

the expression (a/b)*b + a%b shall equal a

dbush
  • 205,898
  • 23
  • 218
  • 273
  • [Signed remainder of C-style division is as much of a modulo operator as unsigned remainder.](https://en.wikipedia.org/wiki/Modulo_operation) If you want a real mathematician’s modulo, then the result should be an equivalence class. E.g., x modulo y is the set of all integers n such that n is equivalent to x modulo 3, a.k.a. { n | ∃ k∈Z : n = x+ky }. Thus, the result is a not a single number but a set. Mathematicians may write this set as [x]_y, where “_y” denotes y as a subscript. [x]_y = { n | ∃ k∈Z : n = x+ky }. Then [−28]_128 = [100]_128; they are the same set… – Eric Postpischil Nov 17 '21 at 19:45
  • … So the x in [x] is just a representative, and mathematicians are not picky about which representative is chosen. It is only when modulo is adapted to computation and a single representative of the entire is needed that a choice must be made. Then, as far as mathematicians are concerned, any operation that returns a correct representative is a proxy for the modulo operation. (Only a proxy because, as explained above, the true result would be a set.) – Eric Postpischil Nov 17 '21 at 19:47
  • @EricPostpischil: A proper modulo operation should be designed such that (x%m) and (y%m) will be equal if x is congruent to y mod m. For many purposes, the most convenient such operation would map the equivalence classes to integers in the range 0 to m-1, inclusive, but for some other applications one that went from floor(-m/2) to floor((m-1)/2) could also be handy. An operation which maps objects which are congruent mod m into different values, however, isn't really a modulo operation. – supercat Nov 24 '21 at 22:00