## Overview

Instructor | Dr. Armin Straub
MSPB 313 straub@southalabama.edu (251) 460-7262 (please use e-mail whenever possible) |

Office hours | MWF, 9-11am, 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 26 Wednesday, April 15 (previously: April 8) |

Final exam | Wednesday, May 6 — 1:00-3:00pm |

Online grades | USAonline |

Syllabus | syllabus.pdf |

Online questions | https://piazza.com/southalabama/spring2020/ma481 |

## 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). - 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.

The homework system is written by myself in the hope that you find it beneficial. Please help make it as useful as possible by letting me know about any issues!

Date | Sketch | Homework |
---|---|---|

01/13 | lecture01.pdf | Homework Set 1: Problems 1-6 (due 1/24) |

01/15 | lecture02.pdf | Homework Set 1: Problems 7-9 (due 1/24)
The first homework set is now complete, so the due date is final. |

01/17 | lecture03.pdf | Homework Set 2: Problems 1-4 (due 2/3) |

01/22 | lecture04.pdf | Homework Set 2: Problem 5 (due 2/3) |

01/24 | lecture05.pdf | Homework Set 2: Problems 6-11 (due 2/3)
This homework set is now complete, so the due date is final. |

01/27 | lecture06.pdf | Homework Set 3: Problems 1-2 (due 2/10) |

01/29 | lecture07.pdf | Homework Set 3: Problem 3 (due 2/10) |

01/31 | lecture08.pdf | Homework Set 3: Problem 4 (due 2/10) |

02/03 | lecture09.pdf | Homework Set 3: Problem 5 (due 2/10)
This homework set is now complete, so the due date is final. |

02/05 | lecture10.pdf | Homework Set 4: Problems 1-2 (due 2/17) |

02/07 | lecture11.pdf | Homework Set 4: Problems 3-4 (due 2/17) |

02/10 | lecture12.pdf | Homework Set 4: Problems 5-9 (due 2/17)
This homework set is now complete, so the due date is final. |

02/12 | lecture13.pdf | new homework after next class |

02/14 | lecture14.pdf | Homework Set 5: Problem 1 (due 2/26) |

02/17 | lecture15.pdf | Homework Set 5: Problem 2 (due 2/26) |

02/10 | lecture16.pdf | Homework Set 5: Problem 3 (due 2/26)
This (short) homework set is now complete, so the due date is final. |

02/21 | lecture17.pdf | finish all homework |

02/24 | review | start preparing for the midterm exam on 2/26:
midterm01-practice-lecture.pdf (compiled from lectures) Online practice problems (compiled from homework) midterm01-practice.pdf (solutions below) retake quiz (posted below) |

lectures-1-17.pdf (all lecture sketches up to now in one big file) | ||

02/28 | lecture18.pdf | Homework Set 6: Problems 1-2 (due 3/30) |

03/02 | lecture19.pdf | new homework after next class |

03/04 | lecture20.pdf | Homework Set 6: Problems 3-4 (due 3/30) |

03/06 | lecture21.pdf | Homework Set 6: Problems 5-6 (due 3/30) |

Corona induced extra break | ||

03/23 | lecture22.pdf | Homework Set 6: Problems 7-8 (due 3/30)
lecture22-homework-help.pdf This homework set is now complete, so the due date is final. lecture22-1-multiply.mp4 lecture22-2-inversion.mp4 |

03/25 | lecture23.pdf | Homework Set 7: Problems 1-4 (due 4/6)
lecture23-homework-help.pdf AES Explained - Computerphile The AES Block Cipher - Dan Boneh |

03/27 | lecture24.pdf | Homework Set 7: Problem 5 (due 4/6)
lecture24-homework-help.pdf lecture24-multiplicative-order.mp4 |

03/30 | lecture25.pdf | Homework Set 7: Problems 6-8 (due 4/6)
lecture25-homework-help.pdf This homework set is now complete, so the due date is final. lecture25-multiplicative-order-2.mp4 |

04/01 | lecture26.pdf | Homework Set 8: Problems 1-5 (due 4/15)
lecture26-homework-help.pdf lecture26-primitive-roots.mp4 lecture26-rsa.mp4 |

04/03 | lecture27.pdf | Homework Set 8: Problem 6 (due 4/15)
lecture27-homework-help.pdf lecture27-rsa-comments.mp4 |

04/06 | lecture28.pdf | Homework Set 8: Problems 7-11 (due 4/15)
lecture28-homework-help.pdf lecture28-diffie-hellman.mp4 lecture28-elgamal.mp4 |

04/08 | lecture29.pdf | Homework Set 8: Problem 12 (due 4/15)
This homework set is now complete, so the due date is final. lecture29-homework-help.pdf lecture29-elgamal-comments.mp4 |

04/10 | lecture30.pdf | finish all homework |

04/13 | review | get ready for the midterm exam on Wednesday 4/15:
Online practice problems midterm02-practice.pdf (solutions below) |

lectures-18-30.pdf (all lecture sketches since the previous midterm in one big file) | ||

04/17 | lecture31.pdf | Homework Set 9: Problem 1 (due 5/1)
lecture31-homework-help.pdf lecture31-hash-functions.mp4 lecture31-merkle-damgard.mp4 |

04/20 | lecture32.pdf | work through Examples 201, 202, 203
lecture32-passwords.mp4 |

04/22 | lecture33.pdf | Homework Set 9: Problems 2-3 (due 5/1)
lecture33-homework-help.pdf lecture33-digital-signatures.mp4 |

04/24 | lecture34.pdf | finish all homework
lecture34-birthday-paradox.mp4 |

04/27 | lecture35.pdf | start reviewing for the final exam
Riemann Hypothesis - Numberphile Visualizing the Riemann hypothesis and analytic continuation - 3blue1brown The Riemann Hypothesis - Jeff Vaaler P vs. NP and the Computational Complexity Zoo - Hackerdashery What Computers Can't Do - Kevin Buzzard |

04/29 | lecture36.pdf | continue reviewing for the final exam
From Mathematical Magic to Secure Communication - Dan Boneh |

05/01 | review | get ready for the final exam
Online practice problems final-practice.pdf (solutions below) |

lectures-31-36.pdf (all lecture sketches since the previous midterm in one big file) |

## Videos

Videos complementing the lecture sketches are posted to Panopto and can be accessed in USAonline. Links to the recordings are also included next to the lecture sketches above.

This is my first time making and posting videos, so please share all issues or suggestions!

Additional videos are suggested on Piazza.

## 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. The exam schedule is posted in the syllabus and at the top of this page.

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:
- Final Exam:

## Quizzes and solutions

## 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)
- 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.

Each project should have either a computational part (this is a great chance to play with Sage!) or have a more mathematical component. Here are some ideas:

- 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. What proportions do you observe numerically?
- Using frequency analysis (letters, digrams, trigrams and such), can you (more or less automatically) distinguish, say, different languages or maybe even individual authors. This would be a computational project. The exact focus is up to you.
- What are the periods of LFSRs and LCGs? When are they maximal? Discuss mathematical results in the spirit of what is hinted at in Example 52 (for LCGs) and Example 58 (for LFSRs).
- When we say that a pseudorandom generator should have good statistical properties, what exactly do we mean? What tests do people apply in practice to evaluate pseudorandom generators?
- Go into more detail on the prime number theorem. How is it related to the Riemann zeta function and the Riemann hypothesis (this is advanced math)? What goes into its proof? Explore it numerically.
- Discuss finite fields and their classification. This would be a more mathematical project and should include proving basic results on finite fields.
- Describe the main ideas involved in finding the first collision found for SHA-1
- Introduce RSA-OAEP, which is RSA in randomized form with padding.
- Discuss Frobenius pseudoprimes, which feature in a 1998 primality test by Jon Grantham. You could either include mathematical details, such as proofs, or implement the primality test and experimentally analyze the failure rate.