Class 23: Cryptosystems
Schedule
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)
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