Ring

A ring (R, +, \cdot) is a non empty set, with two binary operations + and \cdot that fulfills the following conditions:

1. (R, +) is a group
2. (R, \cdot) is a semigroup
3. The distributive rules hold for every a,b,c\in\mathbb{Z}_{n}:
   • a \cdot (b+c) \equiv (a\cdot b) + (a\cdot c) \pmod{n}
   • (a+b) \cdot c \equiv (a\cdot c) + (b\cdot c) \pmod{n}

Basically a group but with two binary operations, instead of one.

Field

Polynomial division over residue class fields

That's Polynomial Division with Rest. The main take away here would be, if we have two polynomials f, g \in K[x], then the following holds:

1. If deg(f) < deg(g), then: q(x) = 0 and r(x) = f(x), i.e. the result is 0 \text{ Rest:} f(x)
2. If deg(f) \geq deg(g), then do the polynomial division thingy

Lagrange Interpolation Theorem

Note: Only learn the concept behind that. The theorem is not part of the exam.

Is used to calculate a polynomial that runs through a given set of points (a, b), i.e. calculate p(a_i) = b_i for all i \in {1,\dots ,n}

This is done via:

\begin{align} p(x) &= \sum^{n}_{i=1} b_i \cdot L_i(x)\\ \\ L_i(x) &= \prod_{j=1,j \not= i}^n \frac{x-a_j}{a_i - a_j} = \frac{x-a_1}{a_i-a_1} \cdot \ldots \cdot \frac{x-a_{i-1}}{a_i-a_{i-1}} \cdot \frac{x-a_{i+1}}{a_i-a_{i+1}} \cdot \ldots \cdot \frac{x-a_n}{a_i-a_n}. \end{align}