CS 340/Math 340, Applicable algebra

Spring semester 2025

The Course Announcement:

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.
• Even a QR codes can lose bits and convey correct information. The same with deep space communication. Again there are error correcting codes at work.
• 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 perfectly 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, finite fields 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 is in the course bulletin.
Professor: Richard Ehrenborg.

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 2025. If you are unable to register for CS 340, try registering for Math 340.