CS 340/Math 340, Applicable algebra

Spring semester 2008

The class is still open! However the CS 340 part is full. (Of some reasons only 10 students can registrar for CS 340.) But there is still space in the Math 340, so sign up for that part.

This course is cross-registered between Computer Science and Mathematics.

Here are some of the basic questions of modern life:

• Is it safe to use your credit card number on the internet? Or isn't it? The answer relies on Public Key Cryptography.
• RSA is the first such crypto-system. We will explain why it works.
• The security of RSA relies on that it is hard to factor large integers. But if you would like to factor them, how could you do it? We explain the Pollard rho method. (This is in case you would like to break RSA.)
• But if you would like to design your own RSA system, you need to find LARGE prime numbers. How do you find large prime numbers? How do you test that a large number is a prime number?
• How come the music from your cd player sounds perfect, even though there might be dust or scratches on the cd? The answer is error correcting codes.
• We will explain Hamming codes which are able to correct one error.
• If time permits, we will introduce BCH codes which are able to correct more than one error.

Here are some other interesting questions:

• Why after shuffling a deck of cards eight times are you back where you started?
• The hat problem: Three men are assigned hats in two colors, red and blue. Each men can see the hats of the other two men, but not his own hat. They win a million dollars if they can guess their own hat color, but they lose if anyone guesses wrong. What is their optimal strategy?
• What do cicadas know about prime numbers?

The topics of this class are:

• Number theory, including Euclid's algorithm and Fermat's little theorem. (The little, not the last!)
• RSA and key-exchange.
• Pollard rho method.
• Pseudo primes and Carmichael numbers.
• Hamming codes.
• Polynomials, rings and fields.
• Field extensions and BCH codes.

Textbook: A Concrete Introduction to Higher Algebra by Lindsay Childs, Springer-Verlag.
Prerequisite: Matrices and vectors. Math 322 or Math 213 for instance.
The course bulletin: Here is the short course description that are in the course bulletin.
Professor: Richard Ehrenborg.

The class is meeting at 1pm Monday, Wednesday and Friday. As of December 5th, the classroom is Whitehall Classroom Building 345. (It is easy to remember the room number, since 3 squared plus 4 squared is 5 squared.)

The course also counts towards a math minor. This follows from the rule "Six additional hours of mathematics courses numbered greater than 213."

I look forward to seeing you in January 2008. If you are unable to register for CS 340, try registering for Math 340.