Modulo arithmetic

  • This problem is based on the Math concept of modulo arithmetic

  • Modulo arithmetic is arithmetic that produces results within the range of [0 .. (N-1)]

  • Modulo arithmetic is performed using the % operation: 

      a ⊕ b = (a + b) % N  + k×N

  a ⊖ b = (a - b) % N  + k×N

    where you need to add some k multiples of N to bring the result back to range [0 .. (N-1)]

How to perform modulo arithmetic with computer program

  

            a ⊕ b = (a + b) % N  + k×N    for some k where 0 ≤ a ⊕ b < N

  Implementation:

      if (0 ≤ a < N) && (0 ≤ b < N) then:

            a ⊕ b = (a + b) % N



            a ⊖ b = (a - b) % N  + k×N    for some k where 0 ≤ a ⊕ b < N

  Implementation:

      if (0 ≤ a < N) && (0 ≤ b < N) then:

            a ⊕ b = (a - b + N) % N  (+N makes sure that -b+N is positive)

Modulo arithmetic   properties

  • Modulo arithmetic is reversable: 

      a ⊕ b = z   <===>  z ⊖ a = b  ∧ z ⊖ b = a

  • Example: 

      (20 + 7) % 26 = 1 

  Then:

      (1 - 20) % 26 = -19 ≡ -19 + 26 =  7
      (1 -  7) % 26 =  -6 ≡  -6 + 26 = 20

The modulo shift function is reversible 

ShiftAmount = 3*Position + K

     01234567890123456789012345
    "ABCDEFGHIJKLMNOPQRSTUVWXYZ"

For example, ZOOM encoded when K = 3: 

    Z = 25    ShiftAmount = 3*1 + 3 = 6
       + 6
      ----
        31 % 26 = 5 ---> F 

 Reverse:

    F =  5     
       - 6 
      ----
        -1 % 26 = (-1 + 26) = 25 ---> Z

The modulo shift function is reversible 

ShiftAmount = 3*Position + K

     01234567890123456789012345
    "ABCDEFGHIJKLMNOPQRSTUVWXYZ"

For example, ZOOM encoded when K = 3: 

    O = 14    ShiftAmount = 3*2 + 3 = 9
       + 9
      ----
        23 % 26 = 23 ---> X 

 Reverse:

    X = 23     
       - 9 
      ----
        14 % 26 = 14  ---> O

Solution for J4    Use modulo arithmetic to reverse the shift 

   #define S(P) (3*(P) + K)

   // key is used to map 0 <--> 'A', 1 <--> 'B', and so on !
   string key = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"; // key[0] = "A", and so on !

   cin >> K;    // Length of coded input string
   cin >> inp;  // Coded input string

   for ( int i = 0; i < inp.size(); i++ )
   {
      x = inp[i] - 'A';            // x = position
      shift = S(i+1);              // shift performed on character
      y = (x - shift + 26) % 26;   // shift BACK !
      cout << key[y];              // Print decoded character
   }