MATH 342, Section 921: Algebra, Coding Theory, and Cryptography

The final exam will be on Friday, June 16 from 3:00-5:30 PM in the usual classroom, LSK 201. For the exam, all you need to bring is your student ID and something to write with. Remember that there will be no makeup exam. Fair warning: you will not be permitted to leave the exam room during the final exam.

For the exam, all the paper you need will be provided for you. No notes, books, calculators, or other aids are allowed; please do not bring cell phones, pagers, alarm watches, or anything else that would make noise during the midterm. You may wish to ensure that you are familiar with UBC's Academic Regulations pertaining to misconduct during exams.

Reading and homework

Friday, June 16: FINAL EXAM
Thursday, June 15: review
Quiz #5: Wednesday, June 14 on all cryptography material
Solutions to Quiz #5 are now posted
Tuesday, June 13: this modular exponentiation applet can help you check your answers to homework problems
assigned Friday, June 9
Reading: the rest of the RSA article
Homework: some problems on RSA specially written for you!
assigned Thursday, June 8
Reading: sections I, II, III, V, VI, and VII of this article: R. L. Rivest, A. Shamir, and L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Comm. ACM 21 (1978), no. 2, 120–126. Copyright ACM; reprinting privileges by permission of the Association for Computing Machinery.
Homework: check your previous homework problem answers using this affine cipher applet
Quiz #4: Wednesday, June 7 on Chapters 7 (syndrome decoding) and 8
Solutions to Quiz #4 are now posted
assigned Tuesday, June 6
Reading: this excerpt from Ramanujachary Kumanduri and Cristina Romero, Number Theory with Computer Applications, Prentice Hall (Upper Saddle River, New Jersey), 1998, ISBN 0-13-801812-X, pp. 131–134
Homework: Koshy, page 408, problems 9, 11, 13, 15, 17, 21
assigned Friday, June 2
Reading: this excerpt from Thomas Koshy, Elementary Number Theory with Applications, Harcourt/Academic Press (Burlington, Massachusetts), 2002, ISBN 0-12-421171-2, pp. 397–408. Emphasize the last section, on Affine Ciphers.
Homework: pages 93–94, problems 8.5, 8.7, 8.8, 8.10, 8.11(a)
assigned Thursday, June 1
Reading: Hill, pages 86–92
Homework: pages 93–94, problems 8.1, 8.2, 8.3, 8.6, 8.9
Quiz #3: Wednesday, May 31 on Chapters 5, 6 (except for calculations of probabilities for error correction/detection), and 7 (except for syndrome decoding)
Solutions to Quiz #3 are now posted
assigned Tuesday, May 30
Reading: Hill, pages 81–86
Homework:
assigned Friday, May 26
Reading: Hill, pages 71–78
Homework: pages 78–80, problems 7.1, 7.2, 7.8, 7.9, 7.11
assigned Thursday, May 26
Reading: Hill, pages 67–71
Homework: catch up on all homework problems already assigned
Quiz #2: Wednesday, May 24 on Chapters 3–5, except for Equivalence of linear codes
Solutions to Quiz #2 are now posted
assigned Tuesday, May 23
Reading: Hill, pages 60–65 (emphasis on Shannon's Theorem)
Homework: page 65, problems 6.1 and 6.3
assigned Friday, May 19
Reading: Hill, pages 55–59
Homework: pages 53–54, problems 5.1, 5.2, 5.6, 5.7, 5.10
assigned Thursday, May 18
Reading: Hill, pages 47–53
Homework:
Quiz #1: Wednesday, May 17 on Chapters 1–2
Solutions to Quiz #1 are now posted
assigned Tuesday, May 16
Reading: Hill, pages 36–38 and 41–44
Homework: pages 38–39, problems 3.1, 3.2, 3.3, 3.8
assigned Friday, May 12
Reading: Hill, pages 31–36
Homework:
assigned Thursday, May 11
Reading: Hill, pages 18–26
Homework:
assigned Wednesday, May 10
Reading: Hill, pages 11–18
Homework:
assigned Tuesday, May 9
Reading: Hill, pages xi–xii and Chapter 1
Homework: page 10, problems 1.2 and 1.3

Course information

When: Tuesdays, Thursdays, and Fridays, 3:00–4:50 PM and Wednesdays 3:00–3:50 PM
Where: LSK 201 (Leonard S. Klinck building)
Textbook: R. Hill, A First Course in Coding Theory (Oxford University Press)—required
Prerequisites: A passing mark in a linear algebra class: one of MATH 221, MATH 223, or MATH 152. We'll be doing matrix computations quite a bit during the course.

Instructor: Prof. Greg Martin
Office: MATH 212 (Mathematics Building)
Email address: gerg@math.ubc.ca
Phone number: (604) 822-4371
Office hours: Tuesdays and Fridays, 11 PM–noon (note: for those taking MATH 302 this summer, you can come to my office right after that class ends at 11:50—I'll have some time to answer your questions even if it goes past noon)

Course description: This course is an introduction to coding-theory (error-correcting codes) and cryptography, with the necessary mathematical background covered along the way. About two-thirds of the term will be spent on coding theory, and the remaining one-third on cryptography. Students will master both algorithmic techniques (computation) and abstract arguments (proofs).

The coding theory information will come from the textbook by Hill, mainly chapters 1–8, covering topics including vector spaces over finite fields, linear codes, dual codes, parity-check matrices, and Hamming codes. The cryptography information will include affine ciphers, RSA cryptography, and Diffie–Hellman public key exchange; for this part of the course, supplemental notes will be posted on this website for free use by students.

Evaluation: Homework will be given, so that you can practice and verify your understanding and skills, but it will not be collected. There will be five in-class quizzes and a final exam. The course mark will be computed as follows:

Your lowest in-class quiz score will automatically be dropped, and the other four quizzes will be averaged together to form the quiz component of your final mark. (So each of your four best quiz scores will count 12.5 percent towards your final mark.)

Please bring your student ID to every quiz and to the final exam. You are required to be present at all quizzes and at the final exam. No makeup tests will be given. Non-attendance at a quiz or exam will result in a mark of zero being recorded. Unavoidable, documented medical emergencies are the only exception to this policy. Travel plans will not be considered a valid excuse.

Advice for success: