Tuesday 27 September class

Topics:
• Warmup for RSA (although the connection will not be made until next time):
   Find two integers d and y such that 11d - 8y = 1. (There are infinitely many solutions, in fact.) It turns out that the solution with the smallest integers (in absolute value)  is d=3, y=4. There is also an easy way to generate other solutions once you have one: add a multiple of 8 to d and add the same multiple of 11 to y. (It can be proved that this always works.)

• We discussed some of the homework problems, specifically, what in the multiplication table mod 4 is problematic.

The problem with using a modulus that is not prime is that there will be products which are 0 but where the factors are both non-zero.  (These are called zero divisors.) In mod 4, we have 2•2 ≡ 0. This means that there is no "zero product principle" in that number system: if a•b = 0, it is not necessarily true that a=0 or b=0.

• Warmup for RSA (although the connection will not be made until next time):
   Find two integers d and y such that 11d - 8y = 1. (There are infinitely many solutions, in fact.) It turns out that the solution with the smallest integers (in absolute value)  is d=3, y=4. There is also an easy way to generate other solutions once you have one: add a multiple of 8 to d and add the same multiple of 11 to y. (It can be proved that this always works.)
Note: In general, an equation which is to be solved for solutions in the integers is called a Diophantine equation. We will see another example (coming from the Pythagorean Theorem) later in the course.

• Note that when we use the word "code" or "coding" in what follows, it does not always mean that we are trying to keep something a secret! See these Wikipedia articles about code and coding theory.

• UPCs (Universal Product Codes) as an application of modular arithmetic: modular arithmetic is employed to check that the code has been entered correctly. In a 12-digit UPC, the first 6 digits represent the company that makes the product, and the next 5 digits represent the product itself. The last digit is a check digit, chosen so that a certain sum will be congruent to 0 mod 10.

If we call the digits d₁, d₂,d₃,..., d₁₂, then the checksum is
 3d₁ + d₂ + 3d₃ + d₄ + 3d₅ + d₆ + ... + 3d₁₁ + d₁₂
and we require that this checksum be ≡ 0 (mod 10)

We checked some examples in class and also checked to see what happened when we reversed two of the digits in a UPC (an easy mistake to make). When two adjacent nonzero digits were reversed, the checksum was no longer ≡ 0 (mod 10).

This sort of checksum catches many (most?) errors but there are some errors that it will not catch. This is a tradeoff: we want the checking process to be simple and quick (not to waste time) but we also want to catch as many errors as possible. A more elaborate checking process might catch more errors but also would take more time to carry out. In each case of a coding like this (ISBNs, credit card numbers, account numbers, etc.) a decision has to be made how to balance out these two concerns.


Homework:
• Journal assignment: Write up what you learned about the purpose of the checksum for a UPC. How does it check for errors? Why is it important to check for errors? You may want to see if you can find out what kind of checksums are used for other important numbers, such as ISBNs.

Also use your journal (as always) to work out concepts in the lesson that may not be clear to you.

• Problems on UPCs: these are all based on real UPCs, and all the real UPCs I have found so far begin with 0. I don't know why that is.
1) Is each of the following a valid UPC or not?  (I've put spaces in them to represent how they are usually shown on the products these days.)
    a) 0 28367 82855 9
    b) 0 75063 01114 0
2) Find the check digit for the UPC:  (if you have any doubt about how to do this, consult the Wikipedia article - remember that you want the checksum to be congruent to 0 mod 10)
    a) 0 28367 82903 _
    b) 0 50428 10148 _
3) The UPC for a product is  0 50428 32193 5
   Explain why the checksum will not catch the following errors:
    a) 0 50428 39123 5
    b) 0 50428 19323 5
4)(Based on a problem from The Heart of Mathematics)
A friend with bad handwriting writes down a UPC. Unfortunately, you can't tell his 4's from his 9's (they look alike), or his 1's from his 7's (they also look alike). If the code looks like 903068823517, is there any way you can figure out what the real UPC is? If so, what do you do and what is the real UPC? If it is not possible to determine the correct UPC, explain why.

• Next topic is the RSA algorithm for encoding a message to be sent, for security purposes. Make sure that you read this RSA algorithm background article (from Slate).

There will be three phases of discussion of the RSA algorithm:
    First, how it is carried out. We will do this next time with two examples.
    Second, how we find the two public keys and the private key. That's coming up later. And then finally:
    Third, how to prove that the algorithm works.

My notes were handed out in class and are also available here.  You could take look through the first page, after reading the background article linked above.  We will also use this reading from Serge Matovic's homepage. (Section 2 and Section 3 where he encodes and decodes the message. He shows how to use a calculator and some tricks to find the remainder we need.)