```python
# Shabat, IUM, spring 2019, Algebra-2 course, excercises 5.2 and 5.3
# Generic code for displaying multiplication tables
import itertools as it
from IPython.core.display import Latex, Math
import sympy as sp
import pandas as pd
from tabulate import tabulate
```


```python
# sp.init_printing()
```


```python
x = sp.symbols("x")
```


```python
def zero_polynomial(p):
    F_p = sp.FF(p)
    return sp.Poly([], x, domain=F_p)


def iter_all_polynomials(p, deg):
    F_p = sp.FF(p)
    all_scalars = [F_p(n) for n in range(p)]
    powers = [x**n for n in range(deg + 1)]
    for coeff_tuple in it.product(all_scalars, repeat=deg + 1):
        if coeff_tuple[0] == 0:
            continue
        yield sp.Poly(coeff_tuple, x, domain=F_p)


def expr_product(exprs):
    res = exprs[0].as_expr()
    for expr in exprs[1:]:
        res *= expr.as_expr()
    return res


def iter_all_polynomials_with_factorings(p, max_deg):
    table = {}
    for f in iter_all_polynomials(p, 1):
        table[f] = (f,)
        yield f, (f,)
    for deg in range(2, max_deg + 1):
        for f, f_factors in list(table.items()):
            for g, g_factors in list(table.items()):
                h = f * g
                if h.degree() == deg:
                    table[h] = (*f_factors, *g_factors)
        for f in iter_all_polynomials(p, deg):
            f_factors = table.setdefault(f, (f, ))
            yield f, f_factors
            

def return_dict(generator):
    def func(*args, **kwargs):
        return dict(generator(*args, **kwargs))
    return func


@return_dict
def as_table(polynomials_with_factorings):
    for f, f_factors in polynomials_with_factorings:
        yield f.as_expr(), expr_product(f_factors)


def sympy_to_latex(v):
    return "$" + sp.latex(v) + "$"


display(pd.Series(as_table(iter_all_polynomials_with_factorings(2, 3))))
display(pd.Series(as_table(iter_all_polynomials_with_factorings(3, 2))))
```


    x                                           x
    x + 1                                   x + 1
    x**2                                     x**2
    x**2 + 1                           (x + 1)**2
    x**2 + x                            x*(x + 1)
    x**2 + x + 1                     x**2 + x + 1
    x**3                                     x**3
    x**3 + 1               (x + 1)*(x**2 + x + 1)
    x**3 + x                         x*(x + 1)**2
    x**3 + x + 1                     x**3 + x + 1
    x**3 + x**2                      x**2*(x + 1)
    x**3 + x**2 + 1               x**3 + x**2 + 1
    x**3 + x**2 + x              x*(x**2 + x + 1)
    x**3 + x**2 + x + 1                (x + 1)**3
    dtype: object



    x                               x
    x + 1                       x + 1
    x - 1                       x - 1
    -x                             -x
    1 - x                       1 - x
    -x - 1                     -x - 1
    x**2                         x**2
    x**2 + 1                 x**2 + 1
    x**2 - 1         (1 - x)*(-x - 1)
    x**2 + x              -x*(-x - 1)
    x**2 + x + 1           (1 - x)**2
    x**2 + x - 1         x**2 + x - 1
    x**2 - x               -x*(1 - x)
    x**2 - x + 1          (-x - 1)**2
    x**2 - x - 1         x**2 - x - 1
    -x**2                       -x**2
    1 - x**2         (-x - 1)*(x - 1)
    -x**2 - 1               -x**2 - 1
    -x**2 + x               x*(1 - x)
    -x**2 + x + 1       -x**2 + x + 1
    -x**2 + x - 1    (-x - 1)*(x + 1)
    -x**2 - x              x*(-x - 1)
    -x**2 - x + 1       -x**2 - x + 1
    -x**2 - x - 1     (1 - x)*(x - 1)
    dtype: object



```python
def elements_and_multiplication_table(p, f):
    f = sp.Poly(f, domain=sp.FF(p))
    deg = f.degree()
    elements = list(it.chain([zero_polynomial(p)], *[iter_all_polynomials(p, elem_deg) for elem_deg in range(deg)]))
    return [g.as_expr() for g in elements], [[(g * h % f).as_expr() for g in elements] for h in elements]


def as_matrix(e, m):
    return pd.DataFrame(m, columns=list(map(sympy_to_latex, e)), index=list(map(sympy_to_latex, e))).applymap(sympy_to_latex)

e, m = elements_and_multiplication_table(2, x**3 + x**2 + 1)
display(as_matrix(e, m))


e, m = elements_and_multiplication_table(3, x**2 - x - 1)
display(as_matrix(e, m))
```


<div>
<style scoped>
    .dataframe tbody tr th:only-of-type {
        vertical-align: middle;
    }

    .dataframe tbody tr th {
        vertical-align: top;
    }

    .dataframe thead th {
        text-align: right;
    }
</style>
<table border="1" class="dataframe">
  <thead>
    <tr style="text-align: right;">
      <th></th>
      <th>$0$</th>
      <th>$1$</th>
      <th>$x$</th>
      <th>$x + 1$</th>
      <th>$x^{2}$</th>
      <th>$x^{2} + 1$</th>
      <th>$x^{2} + x$</th>
      <th>$x^{2} + x + 1$</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <th>$0$</th>
      <td>$0$</td>
      <td>$0$</td>
      <td>$0$</td>
      <td>$0$</td>
      <td>$0$</td>
      <td>$0$</td>
      <td>$0$</td>
      <td>$0$</td>
    </tr>
    <tr>
      <th>$1$</th>
      <td>$0$</td>
      <td>$1$</td>
      <td>$x$</td>
      <td>$x + 1$</td>
      <td>$x^{2}$</td>
      <td>$x^{2} + 1$</td>
      <td>$x^{2} + x$</td>
      <td>$x^{2} + x + 1$</td>
    </tr>
    <tr>
      <th>$x$</th>
      <td>$0$</td>
      <td>$x$</td>
      <td>$x^{2}$</td>
      <td>$x^{2} + x$</td>
      <td>$x^{2} + 1$</td>
      <td>$x^{2} + x + 1$</td>
      <td>$1$</td>
      <td>$x + 1$</td>
    </tr>
    <tr>
      <th>$x + 1$</th>
      <td>$0$</td>
      <td>$x + 1$</td>
      <td>$x^{2} + x$</td>
      <td>$x^{2} + 1$</td>
      <td>$1$</td>
      <td>$x$</td>
      <td>$x^{2} + x + 1$</td>
      <td>$x^{2}$</td>
    </tr>
    <tr>
      <th>$x^{2}$</th>
      <td>$0$</td>
      <td>$x^{2}$</td>
      <td>$x^{2} + 1$</td>
      <td>$1$</td>
      <td>$x^{2} + x + 1$</td>
      <td>$x + 1$</td>
      <td>$x$</td>
      <td>$x^{2} + x$</td>
    </tr>
    <tr>
      <th>$x^{2} + 1$</th>
      <td>$0$</td>
      <td>$x^{2} + 1$</td>
      <td>$x^{2} + x + 1$</td>
      <td>$x$</td>
      <td>$x + 1$</td>
      <td>$x^{2} + x$</td>
      <td>$x^{2}$</td>
      <td>$1$</td>
    </tr>
    <tr>
      <th>$x^{2} + x$</th>
      <td>$0$</td>
      <td>$x^{2} + x$</td>
      <td>$1$</td>
      <td>$x^{2} + x + 1$</td>
      <td>$x$</td>
      <td>$x^{2}$</td>
      <td>$x + 1$</td>
      <td>$x^{2} + 1$</td>
    </tr>
    <tr>
      <th>$x^{2} + x + 1$</th>
      <td>$0$</td>
      <td>$x^{2} + x + 1$</td>
      <td>$x + 1$</td>
      <td>$x^{2}$</td>
      <td>$x^{2} + x$</td>
      <td>$1$</td>
      <td>$x^{2} + 1$</td>
      <td>$x$</td>
    </tr>
  </tbody>
</table>
</div>



<div>
<style scoped>
    .dataframe tbody tr th:only-of-type {
        vertical-align: middle;
    }

    .dataframe tbody tr th {
        vertical-align: top;
    }

    .dataframe thead th {
        text-align: right;
    }
</style>
<table border="1" class="dataframe">
  <thead>
    <tr style="text-align: right;">
      <th></th>
      <th>$0$</th>
      <th>$1$</th>
      <th>$-1$</th>
      <th>$x$</th>
      <th>$x + 1$</th>
      <th>$x - 1$</th>
      <th>$- x$</th>
      <th>$1 - x$</th>
      <th>$- x - 1$</th>
    </tr>
  </thead>
  <tbody>
    <tr>
      <th>$0$</th>
      <td>$0$</td>
      <td>$0$</td>
      <td>$0$</td>
      <td>$0$</td>
      <td>$0$</td>
      <td>$0$</td>
      <td>$0$</td>
      <td>$0$</td>
      <td>$0$</td>
    </tr>
    <tr>
      <th>$1$</th>
      <td>$0$</td>
      <td>$1$</td>
      <td>$-1$</td>
      <td>$x$</td>
      <td>$x + 1$</td>
      <td>$x - 1$</td>
      <td>$- x$</td>
      <td>$1 - x$</td>
      <td>$- x - 1$</td>
    </tr>
    <tr>
      <th>$-1$</th>
      <td>$0$</td>
      <td>$-1$</td>
      <td>$1$</td>
      <td>$- x$</td>
      <td>$- x - 1$</td>
      <td>$1 - x$</td>
      <td>$x$</td>
      <td>$x - 1$</td>
      <td>$x + 1$</td>
    </tr>
    <tr>
      <th>$x$</th>
      <td>$0$</td>
      <td>$x$</td>
      <td>$- x$</td>
      <td>$x + 1$</td>
      <td>$1 - x$</td>
      <td>$1$</td>
      <td>$- x - 1$</td>
      <td>$-1$</td>
      <td>$x - 1$</td>
    </tr>
    <tr>
      <th>$x + 1$</th>
      <td>$0$</td>
      <td>$x + 1$</td>
      <td>$- x - 1$</td>
      <td>$1 - x$</td>
      <td>$-1$</td>
      <td>$x$</td>
      <td>$x - 1$</td>
      <td>$- x$</td>
      <td>$1$</td>
    </tr>
    <tr>
      <th>$x - 1$</th>
      <td>$0$</td>
      <td>$x - 1$</td>
      <td>$1 - x$</td>
      <td>$1$</td>
      <td>$x$</td>
      <td>$- x - 1$</td>
      <td>$-1$</td>
      <td>$x + 1$</td>
      <td>$- x$</td>
    </tr>
    <tr>
      <th>$- x$</th>
      <td>$0$</td>
      <td>$- x$</td>
      <td>$x$</td>
      <td>$- x - 1$</td>
      <td>$x - 1$</td>
      <td>$-1$</td>
      <td>$x + 1$</td>
      <td>$1$</td>
      <td>$1 - x$</td>
    </tr>
    <tr>
      <th>$1 - x$</th>
      <td>$0$</td>
      <td>$1 - x$</td>
      <td>$x - 1$</td>
      <td>$-1$</td>
      <td>$- x$</td>
      <td>$x + 1$</td>
      <td>$1$</td>
      <td>$- x - 1$</td>
      <td>$x$</td>
    </tr>
    <tr>
      <th>$- x - 1$</th>
      <td>$0$</td>
      <td>$- x - 1$</td>
      <td>$x + 1$</td>
      <td>$x - 1$</td>
      <td>$1$</td>
      <td>$- x$</td>
      <td>$1 - x$</td>
      <td>$x$</td>
      <td>$-1$</td>
    </tr>
  </tbody>
</table>
</div>


48fd4e6c4e503bf209644110fd5a1824da7e6302
ipynb
Jupyter Notebook
notebooks/finite_field_multiplication.ipynb
tekhnus/misc
cf4c6e29434c546e3c29f24f7bb16a0ac65005f5
Unlicense
notebooks/finite_field_multiplication.ipynb
tekhnus/misc
cf4c6e29434c546e3c29f24f7bb16a0ac65005f5
Unlicense
notebooks/finite_field_multiplication.ipynb
tekhnus/misc
cf4c6e29434c546e3c29f24f7bb16a0ac65005f5
Unlicense
Qwen/Qwen-72B
1. YES
2. YES