Discrete Mathematics

Class 23: Cryptosystems


Here’s the updated (and final) schedule for the rest of the semester:

  • Problem Set 9: due on Friday, 1 December at 6:29pm. (This will be posted on 19 November.)
  • Problem Set ω (this is optional, and not like the others, hence it uncountable number): due on Monday, 4 December at 11:59pm. See the Problem Set ω description for examples from previous students.
  • Final Exam: Thursday, 7 December, 9am-noon (in the normal lecture room)


Genius, stupidity and genius again (the short life of Evariste Galois), by Tope Omitola.

Modular Arithmetic

Definition: A number $a$ is congruent to $b$ modulo $n$ if and only if $n\, | \, (a - b)$. We can write this as $a \equiv b \;\; (\text{mod}; n)$.

Prove: $a \equiv b \;\; (\text{mod}\; n)$ iff $\text{rem}(a, n) = \text{rem}(b, n)$.


Groups, Rings, and Fields

Abelian group: set $R$, with a binary operation $+$:
associative, commutative, additive identity (0), additive inverse ($−a$)

Ring: set $R$, with two binary operations $+$, $\times$: Abelian group under $+$
associative, multiplicative identity (1) under $\times$

TODO: finish