Overview
Instructor | Dr. Armin Straub
MSPB 313 straub@southalabama.edu (251) 460-7262 (please use e-mail whenever possible) |
Office hours | MW, 9:00am-noon, or by appointment |
Lecture | MWF, 1:25-2:15pm, in MSPB 235 |
Midterm exams | The tentative dates for our two midterm exams are:
Wednesday, February 21 Wednesday, April 4 |
Final exam | Wednesday, May 2 — 1:00-3:00pm |
Text |
Introduction to Cryptography with Coding Theory
by Wade Trappe and Lawrence C. Washington (Prentice Hall, 2nd Ed., 2006) |
Online grades | USAonline |
Syllabus | syllabus.pdf |
Lecture sketches and homework
To help you study for this class, I am posting lecture sketches. These are not a substitute for your personal lecture notes or coming to class (for instance, lots of details and motivation are not included in the sketches). I hope that they are useful to you for revisiting the material and for preparing for exams.
After most classes, homework is assigned and posted below.
- You should aim to complete the problems right after class, and before the next class meets.
A 15% penalty applies if homework is submitted after the posted due date. - Homework is submitted online, and you have an unlimited number of attempts. Only the best score is used for your grade.
Most problems have a random component (which allows you to continue practicing throughout the semester without putting your scores at risk). - You are the first to test, and hopefully benefit from, this system, which I have written myself over the break. Please report any issues to make it as useful as possible!
- Collect a bonus point for each mathematical typo you find in the lecture notes (that is not yet fixed online), or by reporting mistakes in the homework system. Each bonus point is worth 1% towards a midterm exam.
Date | Sketch | Homework |
---|---|---|
01/08 | lecture01.pdf | Homework Set 1: Problems 1-8 (due 1/17) |
01/10 | lecture02.pdf | Homework Set 1: Problem 9 (due 1/17) |
01/12 | lecture03.pdf | Homework Set 2: Problems 1-5 (due 1/24) |
01/19 | lecture04.pdf | new homework next week |
01/22 | lecture05.pdf | Homework Set 3: Problems 1-6 (due 1/31) |
01/24 | lecture06.pdf | Homework Set 3: Problems 7-8 (due 1/31) |
01/26 | lecture07.pdf | new homework next week |
01/29 | lecture08.pdf | Homework Set 4: Problems 1-2 (due 2/12) |
01/31 | lecture09.pdf | Homework Set 4: Problem 3 (due 2/12) |
02/02 | lecture10.pdf | Homework Set 4: Problems 4-5 (due 2/12) |
02/05 | lecture11.pdf | Homework Set 5: Problems 1-3 (due 2/19) |
02/07 | lecture12.pdf | Homework Set 5: Problems 4-7 (due 2/19) |
02/09 | lecture13.pdf | Homework Set 5: Problem 8 (due 2/19) |
02/12 | lecture14.pdf | Happy Mardi Gras! |
02/14 | lecture15.pdf | start preparing for the midterm exam next week on 2/21:
midterm01-practice-lecture.pdf (compiled from lectures) Online practice problems (compiled from homework) midterm01-practice.pdf (solutions below) |
02/16 | lecture16.pdf | continue preparing for the midterm; Monday will be review |
02/19 | review | get ready for the midterm on Wednesday! |
02/23 | lecture17.pdf | Homework Set 6: Problems 1-2 (due 3/14) |
02/26 | lecture18.pdf | new homework next class |
02/28 | lecture19.pdf | Homework Set 6: Problems 3-4 (due 3/14) |
03/02 | lecture20.pdf | Homework Set 6: Problems 5-6 (due 3/14) |
03/05 | lecture21.pdf | Homework Set 6: Problems 7-9 (due 3/14) |
03/07 | lecture22.pdf | Homework Set 7: Problems 1-3 (due 3/21) |
03/09 | lecture23.pdf | Homework Set 7: Problems 4-5 (due 3/21) |
03/12 | lecture24.pdf | Homework Set 7: Problem 6 (due 3/21) |
03/14 | lecture25.pdf | Homework Set 8: Problems 1-3 (due 4/4) |
03/16 | lecture26.pdf | work through Example 143 |
03/19 | lecture27.pdf | Homework Set 8: Problems 4-8 (due 4/4) |
03/21 | lecture28.pdf | Homework Set 8: Problems 9-10 (due 4/4) |
03/23 | lecture29.pdf | start preparing for the midterm exam on 4/4:
Online practice problems (compiled from homework) midterm02-practice.pdf (solutions below) |
04/02 | review | get ready for the midterm on Wednesday! |
04/06 | lecture30.pdf | review midterm exam |
04/09 | lecture31.pdf | work through Examples 168 and 169 |
04/11 | lecture32.pdf | work through Examples 172 and 174 |
04/13 | lecture33.pdf | do Example 178; work through Examples 181 and 182 |
04/16 | lecture34.pdf | work through Examples 185 and 187 |
04/18 | lecture35.pdf | Homework Set 9: Problems 1-2 (due 4/27)
first, work through Examples 189 and 192 |
04/20 | lecture36.pdf | finish project (mandatory for 581) |
04/23 | lecture37.pdf | start preparing for the final exam on 5/2:
final-practice.pdf (solutions below) |
04/25 | lecture38.pdf | get ready for the final |
Sage
For more involved calculations, we will explore the open-source free computer algebra system Sage.
If you just want to run a handful quick computations (without saving your work), you can use the text box below.
A convenient way to use Sage more seriously is https://cocalc.com. This free cloud service does not require you to install anything, and you can access your files and computations from any computer as long as you have internet. To do computations, once you are logged in and inside a project, you will need to create a "Sage notebook" as a new file.
Exams and practice material
There will be two in-class midterm exams and a comprehensive final exam. Notes, books, calculators or computers are not allowed during any of the exams.
Our (tentative) exam schedule is:
- Midterm Exam 1: Wednesday, February 21
- Midterm Exam 2: Wednesday, April 4
- Final Exam: Wednesday, May 2 — 1:00-3:00pm
The following material will help you prepare for the exams.
- Midterm Exam 1:
- midterm01-practice-lecture.pdf (these are problems we discussed in class)
- Online practice problems (these are compiled from homework)
- midterm01-practice.pdf, midterm01-practice-solution.pdf (these problems are more exam-like)
- Midterm Exam 2:
- Online practice problems (these are compiled from homework)
- midterm02-practice.pdf, midterm02-practice-solution.pdf (these problems are more exam-like)
- Final Exam:
Projects
If you take this class for graduate credit, you need to complete a project. The idea is to gain additional insight into a topic that you are particularly interested in. Some suggestions for projects are listed further below.
- The outcome of the project should be a short paper (about 4 pages per student)
- in which you introduce the topic, and then
- describe how you explored the topic.
- computations or visualizations you did in, say, Sage,
- working out representative examples, or
- combining different sources to get an overall picture.
- Let me know before spring break which topic you choose for your project.
- (computational) Obtain letter frequencies (especially trigrams and such) from different sources (books, newspaper articles, forum posts, etc.), and investigate if you can (more or less automatically) distinguish, say, different languages or maybe even individual authors. The focus is up to you.
- (mathematical) Discuss results on the periods of LFSRs in the spirit of what is hinted at in Example 56.
- (computational) Implement a pseudorandom generator by combining several LFSRs (similar to CSS). Investigate statistical properties (for instance, do bits and bit pairs appear equally likely), periods and such.
- (story telling/computational) Discuss which PRGs are used in various programming languages. Is it known what the reasons for those choices were?
- (mathematical) Discuss for which n there exists a primitive root modulo n.
- (basic computational) Compute and investigate the number of Fermat liars and/or strong liars. For instance, a theoretical result states that at most a quarter of the residues can be strong liars. In practice?
- (basic computational, basic mathematical) Investigate the number of twin primes and describe some of the developments (there is a mix of heuristic expectations and recent proved advances).
- (basic computational) Implement and test the Fermat and Miller-Rabin primality tests.
- (basic computational) Implement the Blum-Blum-Shub PRG and variations (such as using more than one bit). Discuss practical aspects for using it to securely encrypt messages.
- (mathematical) Discuss Carmichael numbers.
- (mathematical) Discuss finite fields and their classification.
- (basic computational) Discuss the weak keys in DES, and illustrate them with explicit examples.
- (story telling/mathematical) Describe P versus NP.
- Introduce and implement your favorite cipher (you can also use someone else's implementation). Then verify its functionality, and do some basic statistical tests.
- Introduce your favorite mathematical concept (groups, graphs, etc.), theorem or problem. Then demonstrate how Sage can be used to work with that concept, provide evidence for the theorem, or better understand the problem.