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