Cryptography, Information Theory, and Error-Correction. Aiden A. Bruen

Чтение книги онлайн.

СКАЧАТЬ

      This indicates that is so . This is not what we were hoping for: is supposed to be a whole number, namely the remainder when 279936 is divided by 55! However, the calculator has made rounding errors, and we suspect that is 41 (and is 5089). This is easily checked. We can verify that Eq. (3.5) checks out with , since .

      Principle 1 To calculate the remainder of 279936 when divided by 55, perform the division on a calculator and multiply the decimal part by 55. Verify your answer by checking that Eq. (3.5) is satisfied. This also works to get the remainder whenever we divide a positive integer (= positive whole number) by another positive integer .

      Question

      How do we know that is unique? Maybe there are two possible values?

      Go back to Eq. (3.5), and suppose we have two solutions with being positive and and both lying between 0 and 54. So we have

      (3.8)

      (3.9)

      Then . Now, if it follows that . So assume that . Call the larger one , so .

      We now have . Since is at least 1 bigger than , we get that the left side is at least 55. Since and are between 0 and 54, we see that the right side is at most 54. Since , we conclude that the assumption leads to a contradiction. Thus, (and so also ): end of story. As a consequence, to check Eq. (3.5) in the future all we need to do in the case above is to ensure that is divisible by 55.

      Getting back to our main narrative, A transmits the cipher text to B having calculated this from the message . How does B recover from 41? B knows that . Since we are using a public cryptosystem, the enciphering algorithm is public knowledge (in this particular example), the enciphering algorithm is “multiply the message by itself seven times and take the remainder on division by ”: this gives the cipher text 41. B calculates the deciphering index as follows.

      There is a unique positive integer between 1 and 39 such that gives a remainder of 1 when divided by 40. In this case, it turns out that (more on this later) since and 161 leaves a remainder of 1 on division by 40. Here, 40 comes from the fact that and 5, 11 are the factors of .

      To recover the message, B multiplies the cipher text, namely 41, by itself 23 times, gets the remainder on division by 55, and this should give the original message, namely 6. So we are claiming that is divisible by 55.

       We СКАЧАТЬ