# coppersmith

### Thm.4

・$\mathrm{det} (B)$とHowgrave-Graham's Lemma の不等式が常に成り立つとよい。
行列$B$は下三角行列にすると対角成分の積で$\mathrm{det (B)}$を表現できる（$f(x)$がモニックな多項式であるという条件がここで生きてくる）。対角成分は$M, X$に依存する。その次数をうまく表現できれば$\mathrm{det} (B)$もうまく表現できる。

その$M, X$は行列$B$の次元により定められるのでは？？？
ということは行列$B$を構成するパラメータである$m, l$により定められるのでは？？？ここからまず行列$B$を構成するパラメータについて考察した。

・そもそも行列$B$が正方行列にならなければ下三角行列にならないのではと考えた。また、LLLアルゴリズムを後に使うので行列$B$が正方行列になった方が嬉しいのでは？？？

Lem.9より、与えられた次数$\delta$のモニックな多項式$f(x)に対して$パラメータ$m, l$を設定すると、法$M^m$上で同じ解を持つ
$n := (m+1)(l+1)$個の方程式が生成される。これを上から順番に並べて行列$B$を構成するので、行数は$n$となる。とすると、生成される方程式の中で最大の次数を$d_{\mathrm{max}}$としたとき、$n = d_{\mathrm{max}}+1$のとき行列$B$は$n \times n$行列となる。

生成される方程式の次数$d$はLem.9より
$d := \delta i + j$,$(0 \leq i \leq m, 0 \leq j \leq l)$で表現できるので、
$d_{\mathrm{max}} := \delta m + l$
となる。よって、
$(m+1)(l+1) = \delta m + l + 1$のとき行列$B$は正方行列になる。これを整理すると、

\begin{align}
(m+1)(l+1) &= \delta m + l + 1 \\
ml + m + l + 1 &= \delta m + l + 1 \\
ml + m &= \delta m \\
l + 1 &= \delta \\
l &= \delta - 1
\end{align}

となるので、パラメータ$l$が与えられる方程式$f(x)$の次数$\delta - 1$のとき行列$B$が正方行列になることがわかる（$m$には依存しない）。
また、
$n = \delta m + l + 1 = \delta m + (\delta - 1) + 1 = \delta m + \delta$となるので、$n$は$m,\delta$によることがわかる。

これで行列$B$が下三角行列になる条件がわかったので、この条件を用いて$\mathrm{det} (B)$を定義していく。

・Lem.9より、$\mathrm{det} (B) = M^{k(\delta, m) } X^{h(\delta, m)}$となる。
$k(\delta, m) = (l+1) \sum_{z=1}^{m} z = \frac{1}{2} \delta m (m+1) = \frac{1}{2} (\delta m + \delta) m = \frac{1}{2}nm$
$h(\delta,m) = \sum_{z=1}^{n-1} z = \frac{1}{2}(n-1)n$

ゆえに、
$\mathrm{det} (B) = M^{\frac{1}{2}nm} X^{\frac{1}{2}(n-1)n}$
となる。
この式をHowgrave-Graham’s Lemma の不等式に当てはめると、
$2^{\frac{n-1}{4}}(M^{\frac{1}{2}nm} X^{\frac{1}{2}(n-1)n})^{\frac{1}{n}} \leq \frac{M^m}{\sqrt{n}}$
という不等式になる。これを変形し、
\begin{align}
2^{\frac{n-1}{4}}(M^{\frac{1}{2}nm} X^{\frac{1}{2}(n-1)n})^{\frac{1}{n}} &\leq \frac{M^m}{\sqrt{n}} \\
2^{\frac{n-1}{4}}M^{\frac{1}{2}m} X^{\frac{1}{2}(n-1)} &\leq \frac{M^m}{\sqrt{n}} \\
2^{\frac{n-1}{2}} M^{m} X^{(n-1)} &\leq \frac{M^{2m}}{n} \\
2^{\frac{n-1}{2}} X^{n-1} &\leq \frac{M^m}{n}
\end{align}

$n$のみの項を無視することが多いらしいので

\begin{align}
X^{n-1} &\leq M^m \\
X^{\delta m + \delta - 1} &\leq M^m \\
X^{\delta m} X^\delta X^{-1} &\leq M^m \\
X X^{\frac{1}{m}} X^{-\frac{1}{\delta m}} &\leq M^{\frac{1}{\delta}} \\
X X^{\frac{\delta - 1}{\delta m}} &\leq M^{\frac{1}{\delta}} \\
X &\leq X^{-\frac{\delta - 1}{\delta m}} M^{\frac{1}{\delta}} \\
X X^{\frac{\delta - 1}{\delta m}} &\leq M^{\frac{1}{\delta}} \\
\end{align}

$X < M^{\frac{1}{\delta}}$
$X < X^{\frac{\delta - 1}{\delta m}+1}$

これが満たされていると、$x_0$は効率よく求めることができる。
$X X^{\frac{\delta - 1}{\delta m}} \leq M^{\frac{1}{\delta}}$

こうであるとき上の式を満たす。（結論）
$X < M^{\frac{1}{\delta}}$

---

***疑問点***
$X \leq M^{\frac{1}{\delta}}$だからといって、$XX^{\frac{\delta - 1}{\delta m}} \leq M^{\frac{1}{\delta}}$が成立するとは限らないのでは？？？

$$X(1 + \epsilon) < M^{\frac{1}{\delta}} ,(0 < \epsilon)$$
この形から
$$X < M^{\frac{1}{\delta}}$$

↓

$$
\begin{aligned}
X &\lt M^\frac{1}{\delta}\cr
X^{\delta m} &\lt M^m\cr
X^{n-1} = X^{\delta m - 1} \lt X^{\delta m} &\lt M^m\cr
\end{aligned}
$$

---

$X\lt M^\frac{1}{\delta}$のとき, $X\lt X^{\frac{\delta-1}{\delta m} + 1}$は成立. （これ）

$\log _ M X\lt\frac{1}{\delta}$のとき$\frac{\delta(m+1) - 1}{\delta m}\log _ M X\lt\frac{1}{\delta}$は成立するか?

$X^{-\frac{\delta - 1}{\delta m}}$は１より小さいことが確定してしまうので、この方法では$X \leq M^{\frac{1}{\delta}}$を証明することはできない。。。（1より大きかったら嬉しかった）。他の論文やスライドを見る限り、一番最初に正方行列の条件をつけたのがダメだった。。。？あの条件を付けなくても下三角行列$B$の行列式を定式化することができる？？？

### 見直し後

\begin{align}
X X^{\frac{1}{m}} X^{-\frac{1}{\delta m}} &\leq M^{\frac{1}{\delta}} \\
X X^{\frac{\delta - 1}{\delta m}} &\leq M^{\frac{1}{\delta}} \\
\end{align}
ここで$1 \leq \delta, 1 \leq m, 1 \leq X$ならば$1 \leq X^{\frac{\delta - 1}{\delta m}}$であるので
\begin{align}
X X^{\frac{\delta - 1}{\delta m}} &\leq M^{\frac{1}{\delta}} \\
X(1 + \epsilon) &\leq M^{\frac{1}{\delta}} \qquad (0 \leq \epsilon) \\
X \leq X(1 + \epsilon) &\leq M^{\frac{1}{\delta}} \\
X &\leq M^{\frac{1}{\delta}}
\end{align}

という条件式が成り立つ。（絶対値を無視してしまったケース）

ここで係数行列$B$を下三角行列だけでなく係数を雑に並べた行列$B'$を構成してもよいとすると、行と列の入れ替えから$\mathrm{det}(B') = -\mathrm{det}(B)$という行列式がでる可能性がある。それを考慮するため行列式は$|\mathrm{det} (B)|$と絶対値付きで表現するのが望ましい。（というか今資料を読み返してみるとそもそもLLLしたあとの縮小ベクトルのノルムの評価は$|\mathrm{det} (B)|$のように絶対値付きだった。ノルムの長さの評価なんだから絶対値付きになるのは当たり前。。。）

ゆえに絶対値付きで考えると
\begin{align}
|X| &\leq M^{\frac{1}{\delta}}
\end{align}

この条件より
\begin{align}
|X| &\leq M^{\frac{1}{\delta}} \\
-M^{\frac{1}{\delta}} \leq X &\leq M^{\frac{1}{\delta}}　\\
\text{仮定は} \quad |x_0| &\leq X \quad (Xは正の数)なので \\
-M^{\frac{1}{\delta}} \leq -X \leq 0 &\leq X \leq M^{\frac{1}{\delta}}\quad \text{という式変形と}\\
-X \leq x_0 &\leq X \quad \text{から}\\
-M^{\frac{1}{\delta}} \leq x_0 &\leq M^{\frac{1}{\delta}} \quad \text{ゆえに} \\
|x_0| &\leq M^{\frac{1}{\delta}} \\
\end{align}

### Thm.6

とりあえず生成される方程式の法が$M$ではなく未知数$b$に置き換わっていることはわかる。とすると、上の証明から
$$|x_0| \leq b^{\frac{1}{\delta}}$$になりそうなイメージはある。まず証明したい定理を整理する。

___Thm.6___
$N$を既知の整数、$0 \leq \beta \leq 1$を実数とし、$f(x)$をモニックな1変数$\delta$次多項式とする。このとき未知の$b \geq N^\beta,b|N$について、$f(x_0) \equiv 0 \pmod{b}$が成立、かつ次の条件を満たすような$x_0$を多項式時間で求めることができる。
$$|x_0| \leq N^{\frac{\beta^2}{\delta}}$$
ここからわかることは$1 \leq b \leq N$であり、$b$は$N$の約数である。方程式の方が未知の値でも、その倍数がわかっているのなら解くことができる。$\beta$が1の場合、$b=N$なのでThm.4と同一。$\beta$が0の場合$b=1$なので方程式自体が自明？（あんまり関係なさそう。）

とりあえずできそうな式変形を試す。
\begin{align}
b &\leq N \\
b^{\frac{\beta^2}{\delta}} &\leq N^{\frac{\beta^2}{\delta}} \\
\end{align}あんまり関係なさそう。というか、

$$N^{\frac{\beta^2}{\delta}} \leq b^{\frac{1}{\delta}}$$が証明できればいいのか。
式変形して
$$N^{\beta^2} \leq b$$
を証明できればいい。

使えそうな条件は$b \geq N^\beta$かな？
$$N^\beta \leq b$$ $\beta$乗して
$$N^{\beta^2} \leq b^\beta$$
$\beta$は$0 \leq \beta \leq 1$なので$$b^\beta \leq b$$よって
$$N^{\beta^2} \leq b^\beta$$ならば
$$N^{\beta^2} \leq b$$が示せる。
よってThm.6は成立する。あれ、でも$b|N$という条件をあまり活用できていない気が。。。どこか暗黙のうちに使っている？あ、そっか。同じ解を持った方程式を生成するときに使っているのか。だから一番最初に$M$を$b$と置き換えれるのか。

______

$$
\begin{aligned}
2^{\frac{n-1}{4}}\left(N^\frac{\delta m(m+1)}{2}X^\frac{n(n-1)}{2}\right)^\frac{1}{n}&\lt \frac{N^{\beta m}}{\sqrt{n}}\cr
\sqrt{2}\left(N^\frac{\delta m(m+1)}{2}X^\frac{n(n-1)}{2}\right)^\frac{2}{n(n-1)}&\lt \frac{N^\frac{2\beta m}{n-1}}{n^\frac{1}{n-1}}\cr
\sqrt{2}N^\frac{\delta m(m+1)}{n(n-1)}X&\lt \frac{N^\frac{2\beta m}{n-1}}{n^\frac{1}{n-1}}\cr
X&\lt \frac{1}{\sqrt{2}\cdot n^\frac{1}{n-1}}\cdot N^{\frac{2\beta m}{n-1}-\frac{\delta m(m+1)}{n(n-1)}}\cr
\end{aligned}
$$

$$\frac{1}{\sqrt{2} n^{\frac{1}{n-1}}}$$

$2 \leq n$であり、