Front

By what can we reduce the exponent of an element in a finite order Group?

Back

In a group \(G\) of finite order, for \(a \in G\): \[a^m = a^{{{c1::R_{\text{ord}(a)}(m)}}}\]

This holds because {{c2::\(a^m = a^{m + \text{ord}(a)} = a^m \cdot a^{\text{ord}(a)} = a^m \cdot e = a^m\)}}.

Front

\(\mathbb{Z}_m^*\) is defined as?

Back

\[ \overset{\text{def}}{=} \ \{a \in \mathbb{Z}_m \ | \ \gcd(a, m) = 1\} \]

This is the set of all elements in \(\mathbb{Z}_m\) that are coprime to \(m\).

Front

If the prime factorization of \(m\) is \(m = \prod_{i=1}^r p_i^{e_i}\) then \(\varphi(m)\) is?

Back

\[\varphi(m) = \prod_{i=1}^r (p_i - 1)p_i^{e_i - 1}\]

For a prime \(p\) and \(e \geq 1\): \[\varphi(p^e) = {{c2::p^{e-1}(p-1)}}\]

This comes from the fact that for prime \(p\) and \(e \geq 1\) we have \[ \varphi(p^e) = p^{e-1}(p - 1) \]since exactly every \[\varphi(p^e) = {{c2::p^{e-1}(p-1)}}\]0th integer in \[\varphi(p^e) = {{c2::p^{e-1}(p-1)}}\]1 contains a factor \[\varphi(p^e) = {{c2::p^{e-1}(p-1)}}\]2 and thus \[\varphi(p^e) = {{c2::p^{e-1}(p-1)}}\]3 elements don't contain a factor \[\varphi(p^e) = {{c2::p^{e-1}(p-1)}}\]4, i.e. are in \[\varphi(p^e) = {{c2::p^{e-1}(p-1)}}\]5.
Since the \[\varphi(p^e) = {{c2::p^{e-1}(p-1)}}\]6's are pairwise relatively prime (obviously) by the CRT we have that \[\varphi(p^e) = {{c2::p^{e-1}(p-1)}}\]7. This holds as the CRT allows us to establish a bijection between each \[\varphi(p^e) = {{c2::p^{e-1}(p-1)}}\]8 and a unique tuple \[\varphi(p^e) = {{c2::p^{e-1}(p-1)}}\]9 where \[ \varphi(p^e) = p^{e-1}(p - 1) \]0.

Name a zerodivisor in a Ring.

Give an example of an extension field constructed from polynomials.

An encoding function maps \(k\) information symbols to $n encoded symbols.

What is the \((n, k)\)-error correcting code over the alphabet \(\mathcal{A}\) with $|\mathcal{A}| = q?

Front

What is a polynomial over a commutative ring?

Back

A polynomial \(a(x)\) over a commutative ring \(R\) in the indeterminate \(x\) is a formal expression of the form: \[ a(x) = {{c2::a_d x^d + a_{d-1}x^{d-1} + \cdots + a_1 x + a_0}} = \sum_{i=0}^d a_i x^i \] for some non-negative integer \(d\), with \(a_i \in R\).

The set of polynomials in \(x\) over \(R\) is denoted \(R[x]\).

Front

Lagrange Interpolation for polynomials in a Field

Back

Let \(\beta_i = a(\alpha_i)\) for \(i = 1, \dots, d+1\).

Then \(a(x)\) is given by Lagrange's Interpolation formula: \[a(x) = \sum_{i=1}^{d+1} \beta_i u_i(x)\] where the polynomial \(u_i(x)\) is: \[u_i(x) = \frac{{{c2::(x - \alpha_1) \cdots (x - \alpha_{i-1})(x - \alpha_{i+1}) \cdots (x - \alpha_{d+1})}}}{{{c3::(\alpha_i - \alpha_1) \cdots (\alpha_i - \alpha_{i-1})(\alpha_i - \alpha_{i+1}) \cdots (\alpha_i - \alpha_{d+1})}}}\]

Note that for \(u_i(x)\) to be well-defined, all constant terms \(\alpha_i - \alpha_j\) in the denominator must be invertible. This is guaranteed in a field since \(a_i - a_j \neq 0\) for \(i \neq j\) (as they are all distinct).

{{c2::
• Assoziativität: \((a * b) * c = a * (b*c)\)
• Neutrales Element existiert: \( a * e = e * a = a \)
• Jedes Element \(a\in G\) hat eine Inverse: \( a * a^{-1} = a^{-1} * a = e\)
}}