# coppersmith_2

### Thm.4

***仮説（証明したい定理）***

$N$を既知の整数とし、$f(x)$をモニックな1変数$\delta$次多項式とする。このとき、$f(x_0) \equiv 0 \pmod{N}$なる$x_0$が、
$$|x_0| \leq N^{\frac{1}{\delta}}$$の条件を満たすならば、$x_0$は効率よく求めることができる。

***与えれられた条件***
・$x_0$は、$f(x_0) \equiv 0 \pmod{N}$を満たす。
・$x_0$は、$|x_0| \leq N^{\frac{1}{\delta}}$を満たす。

***結論***
・$x_0$は効率よく求めることができる。

______

***証明の方針***
$|x_0|$をある$X$以下であると仮定する。そのときのHow-graham's LemmaやLLLの縮小ベクトルの定理を利用して、$x_0$が効率よく求まるための$X$についての条件を導出する。そのとき$X$が$N^{\frac{1}{\delta}}$以下だった場合、$|x_0| \leq X, X \leq N^{\frac{1}{\delta}}$から$|x_0| \leq N^{\frac{1}{\delta}}$となり$x_0$は効率よく求めることができると示せているので、仮説を証明できる。

***仮定***
・$N$を既知の整数
・$f(x)$をモニックな1変数$\delta$次多項式
・$|x_0| \leq X$（この時点で$X$は0より大きいことが暗黙に決定される）

***導出***
・$x_0$が効率よく求めるための、$X$に関する条件式①を導出する。Xが①を満たすならば、$x_0$は効率よく求めることができる。このとき、①は
$$X \leq N^{\frac{1}{\delta}}$$であると嬉しい。

***ここから得られる定理②（仮定を満たすと得られる事実）***
$N$を既知の整数、$f(x)$をモニックな1変数$\delta$次多項式、$f(x_0) \equiv 0 \pmod{N}$なる$x_0$が、$|x_0| \leq X$であるとする（暗黙に$0 < X$）。このとき、
$$X \leq N^{\frac{1}{\delta}}$$であるならば$x_0$は効率よく求めることができる。

$|x_0| \leq X$かつ$X \leq N^{\frac{1}{\delta}}$ならば$|x_0| \leq N^{\frac{1}{\delta}}$であるので、定理②を言い換えると、

***定理③（定理②を言い換える）***
$N$を既知の整数、$f(x)$をモニックな1変数$\delta$次多項式であるとする。このとき、$f(x_0) \equiv 0 \pmod{N}$なる$x_0$が、
$$|x_0| \leq N^{\frac{1}{\delta}}$$の条件を満たすならば、$x_0$は効率よく求めることができる。

という事実が得られる。
定理③は仮説と同じなので、仮説は証明されたことになる。

______

***証明***
$N$を既知の整数（法なので0より大きい）、$f(x)$をモニックな1変数$\delta$次多項式（1変数多項式なので$1 \leq \delta$）、$f(x_0) \equiv 0 \pmod{N}$なる$x_0$が、$|x_0| \leq X$であるとする（暗黙のうちに$0 < X$）。

Lem.9より生成される方程式から係数行列$B$を構成する。このとき係数の並べ方に特殊な条件をつける。Lem.9のパラメータ$l = \delta - 1$とし、Lem.9で生成される方程式をp61のように並べるとすると、行列$B$は$n \times n,(n = \delta m + \delta))$の下三角行列となる。このとき行列$B$は対角成分の積により$\mathrm{det}(B)$を表すことができるので
$$\mathrm{det} (B) = N^{\frac{1}{2}nm} X^{\frac{1}{2}(n-1)n}$$が成り立つ（古い方のリンクに導出は書いてあるので省略）。
係数の並べ方に条件を付けない一般の行列$B'$に対して、行と列の基本変形より$|\mathrm{det}(B')| = |\mathrm{det}(B)|$である。ゆえに
$$|\mathrm{det} (B')| = |\mathrm{det} (B)| = |N^{\frac{1}{2}nm} X^{\frac{1}{2}(n-1)n}|$$ $N,X$は正の数であるから
$$|\mathrm{det} (B')| = |\mathrm{det} (B)| = N^{\frac{1}{2}nm} X^{\frac{1}{2}(n-1)n}$$であるので、一般の行列$B'$においても議論ができる。
この式を用いてHowgrave-Graham’s LemmaとLLLの縮小ベクトルの定理に当てはめると、
$$2^{\frac{n-1}{4}}(N^{\frac{1}{2}nm} X^{\frac{1}{2}(n-1)n})^{\frac{1}{n}} \leq \frac{N^m}{\sqrt{n}}$$となるので、値が小さい$n$の項を無視して整理すると、
$$X^{\frac{\delta - 1}{\delta m}+1} \leq N^{\frac{1}{\delta}}$$ Lem.9より$1 \leq m$、与えられた条件より$1 \leq \delta$なので$X \leq X^{\frac{\delta - 1}{\delta m}+1}$、
$X \leq X^{\frac{\delta - 1}{\delta m}+1}$かつ$X^{\frac{\delta - 1}{\delta m}+1} \leq N^{\frac{1}{\delta}}$ならば
$$X \leq N^{\frac{1}{\delta}}$$ ゆえに$X$がこの不等式を満たしているならば、$x_0$は効率よく求めることができる。

***以上の証明より言い切れること***
$N$を既知の整数（法なので0より大きい）、$f(x)$をモニックな1変数$\delta$次多項式（1変数多項式なので$1 \leq \delta$）、$f(x_0) \equiv 0 \pmod{N}$なる$x_0$が、$|x_0| \leq X$であり（$x_0$は絶対値付きなので暗黙のうちに$0 < X$）、$X \leq N^{\frac{1}{\delta}}$であるとする。（+α：Lem.9で使う$l = 1-\delta$とする？）
このとき、
$$|x_0| \leq N^{\frac{1}{\delta}}$$を満たし、$x_0$を効率よく求めることができる。

よってThm.4は証明される。
______