$\text{Question}\ 1$
$\text{Description}\ 1$
求 $GF_2[x]$ 上多项式 $f(x)=x^5+x^3+x+1$ 与 $g(x)=x^3+x^2+x+1$ 的最大公因式，并求出多项式 $s(x),t(x)$，使得 $s(x)f(x) + t(x)g(x) = \gcd(f(x),g(x))$，且 $s(x)$ 和 $t(x)$ 的次数分别小于 $g(x)$ 和 $f(x)$ 的次数。
$\text{Answer}\ 1$
\[\begin{align} \text{let}\ &f_1(x)=f(x),\ g_1(x)=g(x)\\ &f_1(x)=q_1(x)g_1(x)+r_1(x)\rightarrow q_1(x)=x^2+x+1,\ r_1(x)=x^2+x\\ \text{let}\ &f_2(x)=g_1(x),\ g_2(x)=r_1(x)&\\ &f_2(x)=q_2(x)g_2(x)+r_2(x)\rightarrow q_2(x)=x,\ r_2(x)=x+1\\ \text{let}\ &f_3(x)=g_2(x),\ g_3(x)=r_2(x)&\\ &f_3(x)=q_3(x)g_3(x)+r_3(x)\rightarrow q_3(x)=x,\ r_3(x)=0\\ \text{then:} &\gcd(f(x),g(x))=g_3(x)=x+1\\ g_3(x)&=f_2(x)+q_2(x)g_2(x)\\ &=g_1(x)+r_1(x)q_2(x)\\ &=g_1(x)+[f_1(x)-g_1(x)q_1(x)]q_2(x)\\ &=g_2(x)f_1(x)+[q_1(x)q_2(x)+1]g_1(x)\\ \text{so}\ &s(x)=q_2(x)=x,\ t(x)=[q_1(x)q_2(x)+1]=x^3+x^2+x+1\\ \end{align}\]$\text{Question}\ 2$
$\text{Description}\ 2$
计算 $8$ 元域 $GF_2[x]/(x^3+x+1)$ 的加法表和乘法表
$\text{Answer}\ 2$
元素集合： ${0,1,x,1+x,x^2,1+x^2,x+x^2,1+x+x^2}$
加法表
| $+$ | $0$ | $1$ | $x$ | $1+x$ | $x^2$ | $1+x^2$ | $x+x^2$ | $1+x+x^2$ |
|---|---|---|---|---|---|---|---|---|
| $0$ | $0$ | $1$ | $x$ | $1+x$ | $x^2$ | $1+x^2$ | $x+x^2$ | $1+x+x^2$ |
| $1$ | $1$ | $0$ | $1+x$ | $x$ | $1+x^2$ | $x^2$ | $1+x+x^2$ | $x+x^2$ |
| $x$ | $x$ | $1+x$ | $0$ | $1$ | $x+x^2$ | $1+x+x^2$ | $x^2$ | $1+x^2$ |
| $1+x$ | $1+x$ | $x$ | $1$ | $0$ | $1+x+x^2$ | $x+x^2$ | $1+x^2$ | $x^2$ |
| $x^2$ | $x^2$ | $1+x^2$ | $x+x^2$ | $1+x+x^2$ | $0$ | $1$ | $x$ | $1+x$ |
| $1+x^2$ | $1+x^2$ | $x^2$ | $1+x+x^2$ | $x+x^2$ | $1$ | $0$ | $1+x$ | $x$ |
| $x+x^2$ | $x+x^2$ | $1+x+x^2$ | $x^2$ | $1+x^2$ | $x$ | $1+x$ | $0$ | $1$ |
| $1+x+x^2$ | $1+x+x^2$ | $x+x^2$ | $1+x^2$ | $x^2$ | $1+x$ | $x$ | $1$ | $0$ |
乘法表
| $\times$ | $0$ | $1$ | $x$ | $1+x$ | $x^2$ | $1+x^2$ | $x+x^2$ | $1+x+x^2$ |
|---|---|---|---|---|---|---|---|---|
| $0$ | $0$ | $0$ | $0$ | $0$ | $0$ | $0$ | $0$ | $0$ |
| $1$ | $0$ | $1$ | $x$ | $1+x$ | $x^2$ | $1+x^2$ | $x+x^2$ | $1+x+x^2$ |
| $x$ | $0$ | $x$ | $x^2$ | $x+x^2$ | $1+x$ | $1$ | $1+x+x^2$ | $1+x^2$ |
| $1+x$ | $0$ | $1+x$ | $x+x^2$ | $1+x^2$ | $1+x+x^2$ | $x^2$ | $1$ | $x$ |
| $x^2$ | $0$ | $x^2$ | $1+x$ | $1+x+x^2$ | $x+x^2$ | $x$ | $1+x^2$ | $1$ |
| $1+x^2$ | $0$ | $1+x^2$ | $1$ | $x^2$ | $x$ | $1+x+x^2$ | $1+x$ | $x+x^2$ |
| $x+x^2$ | $0$ | $x+x^2$ | $1+x+x^2$ | $1$ | $1+x^2$ | $1+x$ | $x$ | $x^2$ |
| $1+x+x^2$ | $0$ | $1+x+x^2$ | $1+x^2$ | $x$ | $1$ | $x+x^2$ | $x^2$ | $1+x$ |
二进制乘法代码
void mul(const bitset<10> &a, const bitset<10> &b) {
bitset<10> result(0);
for (int i = 9; i >= 6; i--) {
if (b[9-i]) {
result ^= (a << (9 - i));
}
}
for (int i = 2; i <= 6; i++) {
if(result[9-i]) {
result ^= (base << (6 - i));
}
}
pt(&result);
}
$\text{Question}\ 3$
$\text{Description}\ 3$
令 $G$ 为群，$e$ 是群 $G$ 中的单位元。$a\in G$，且 $a$ 的阶等于 $n$，即 $ord(a)=n$，证明：集合 $H={e,a,a^2,\cdots, a^{n-1}}$ 为 $G$ 的子群。
$\text{Answer}\ 3$
- 首先证明 $H$ 是群 $G$ 的子集
- $a$ 的阶等于 $n$，所有 $a^n=e$
- $H={a^t \mid 1\le t \le n} \subseteq G$
- 证明 $H$ 是一个群
- 首先集合 $H$ 中存在单位元 $e$
- 对于任意 $x=a^{t},x\not=e$，有 $a^ta^{n-t}=e,a^{n-t}\in H$，故每个元素都有逆元
- 对于任意 $x=a^{t_1},y=a^{t_2}$，$xy=a^{t_1+t_2}$，$2 \le t_1+t_2 \le 2n$
- 当 $2 \le t_1+t_2 \le n$ 时，$a^{t_1+t_2}\in H$，当 $n+1 \le t_1+t_ 2 \le 2n$ 时，$a^{t_1+t_2}=a^{t_1+t_2-n}\in H$，即运算封闭
- 故 $H$ 是群 $G$ 的子群
$\text{Question}\ 4$
$\text{Description}\ 4$
证明 $p^{q-1}+q^{p-1}\equiv1 \pmod{pq}$，这里 $p,q$ 是不同的素数。
$\text{Answer}\ 4$
- 由欧拉定理，有 $p^{q-1}\equiv 1 \pmod q，q^{p-1}\equiv 1 \pmod p$
- 又有$q^{p-1}\equiv 0 \pmod q，p^{q-1}\equiv 0 \pmod p$
- 即 $p^{q-1}+q^{p-1}\equiv1 \pmod{p}，p^{q-1}+q^{p-1}\equiv1 \pmod{q}$
- 则 $p^{q-1}+q^{p-1}\equiv1 \pmod{\text{gcm}(p,q)=pq}$
$\text{Question}\ 5$
$\text{Description}\ 5$
计算 $2^{2022118} \pmod7$。
$\text{Answer}\ 5$
- $2^{\varphi(7)}\equiv1 \pmod 7 \rightarrow 2^6\equiv1 \pmod7$
- $2022118\%6=4$
- $2^{2022118}\equiv2^4\equiv2 \pmod7$
$\text{Question}\ 6$
$\text{Description}\ 6$
计算 $17$ 模 $48$ 的指数 $\text{ord}_{48}(17)$。
$\text{Answer}\ 6$
- $\varphi(48)=\varphi(2^43^1)=48(1-\frac{1}{2})(1-\frac{1}{3})=16$
- 考虑 $16$ 的所有因子 $1，2，4，8，16$
- $17^2\%48=1$，故$\text{ord}_{48}(17)=2$