crypto-writeup-public

Gaussの補題（多項式）

整数係数多項式 $f(x)$ が $\mathbb{Q}\lbrack x\rbrack$ 上で $f = gh$ と因数分解可能である時、 $f(x)$ は $\mathbb{Z}\lbrack x\rbrack$ 上でも因数分解可能である
逆も成り立つ

$g, h$ の係数全体を整数に持ち上げるような定数をそれぞれ $r, s$ とすると $g' = rg \in \mathbb{Z}\lbrack x\rbrack$ , $h' = sh \in \mathbb{Z}\lbrack x \rbrack$ である。このとき $g'h' = df$ となる

$d = 1$ のときOK それ以外の場合 $d = p_1,p_2,\dots$ と表す

$p_i$ からなる $\mathbb{Z_p}\lbrack x \rbrack$ 上で考えると $g'h' \equiv 0$ であるから、 $g', h'$ のいずれかの係数はすべて $p_i$ で割り切れることになる

ここでは $g'$ がそうであると仮定する。このとき、 $g' / p_i$ もまた整数係数であり、 $\mathbb{Z}\lbrack x \rbrack$ に含まれるから、 $r \leftarrow r / p_i$ と置きなおせば良い

このようにして最終的に $rg \cdot sh = f$ を満たす $r, s$ を見つけることができる