# coppersmith_4

______

### Thm.6の証明(結局結論は同じだった)
\begin{align}
2^{\frac{n-1}{4}}(M^{\frac{1}{2}nm} X^{\frac{1}{2}(n-1)n})^{\frac{1}{n}} &\leq \frac{b^m}{\sqrt{n}} \\
(M^{\frac{1}{2}nm} X^{\frac{1}{2}(n-1)n})^{\frac{1}{n}} &\leq b^m \\
M^{\frac{1}{2}m} X^{\frac{1}{2}(n-1)} &\leq b^m \\
M^m X^{n-1} &\leq b^{2m} \\
(kb)^m X^{n-1} &\leq b^{2m} \\
k^m X^{n-1} &\leq b^m \\
k^m X^{\delta m + \delta -1} &\leq b^m\\
k X^\delta X^{\frac{\delta}{m}} X^{-\frac{1}{m}} &\leq b \\
k^{\frac{1}{\delta}} X^{\frac{1}{m}} X^{-\frac{1}{\delta m}} X &\leq b^{\frac{1}{\delta}} \\
k^{\frac{1}{\delta}} X^{\frac{\delta - 1}{\delta m}} X &\leq b^{\frac{1}{\delta}} \\
\end{align}

を満たしているとき、$x_0$を効率よく求めることができる。

______

### 新しいパターンの証明（ちょっとまだ甘いから一旦放置）

$f(x_0) \equiv 0 \pmod{N}$の次数$\delta$の多項式がある。
$$g_{i,j} = x^j N^i f^{m-i}(x) \quad ,(0 \leq i \leq m-1),(0 \leq j \leq \delta - 1)$$
$$h_i(x) = x^i f^m(x) \quad ,(0 \leq i \leq t-1)$$

上の式は$N^m$では同じ解$x_0$をもっている。
このときパラメータは$m,t$。

そして生成した方程式から係数行列$L$を構成する。そのとき,$$||b_1|| \leq 2^{\frac{n-1}{4}} \cdot det(L)^{\frac{1}{n}}$$
Howgrave-Grahamの定理から$$||b_1|| = ||g(xX)|| < \frac{N^m}{\sqrt{n}}$$

とすると、$$2^{\frac{n-1}{4}} \cdot det(L)^{\frac{1}{n}} \leq \frac{N^m}{\sqrt{n}}$$となり、式変形して$$det(L) < 2^{-\frac{n-1}{4}} n^{-\frac{1}{2}}N^m$$ここで、なぜか両辺を$n$乗してから$n$のみの関数を無視している。初めから無視すればいいのに。

結論として、$$det(L) < N^{mn}$$

______

### 論文の意味汲み取り

$f(x) = (m_0 + x)^e - c = 0 \pmod{b}$
また関係は
$b \geq N^\beta,0 < \beta \leq 1, |x_0| < X$
$n = \delta m + t$とする。
いつもの通り
$2^{\frac{n-1}{4}} det(L)^{\frac{1}{n}} < \frac{b^m}{\sqrt{n}}$

ここでパラメータ$b$の代わりに
$2^{\frac{n-1}{4}} det(L)^{\frac{1}{n}} < \frac{N^{\beta m}}{\sqrt{n}}$。

ここでは、
$det(L) = N^{\frac{1}{2} \delta m (m + 1)} X^{\frac{1}{2} n (n - 1)}$
としている。ここで必要になってくるのが先ほどの$h_i(x)$

$f(x_0) \equiv 0 \pmod{N}$の次数$\delta$の多項式がある。
$$g_{i,j} = x^j N^i f^{m-i}(x) \quad ,(0 \leq i \leq m-1),(0 \leq j \leq \delta - 1) \quad ①$$
$$h_i(x) = x^i f^m(x) \quad ,(0 \leq i \leq t-1) \quad ②$$

上の式は$N^m$では同じ解$x_0$をもっている。
このときパラメータは$m,t$。

①について。
生成される方程式の数は$m \times \delta$個。
②について。
生成される方程式の数は$t$個。
よって$n$は①と②から生成される方程式をそのまま全部並べている考えてよさそう。
まあきっとこの並べ方から法則性を見つけたら先ほどの$det(L) = N^{\frac{1}{2} \delta m (m + 1)} X^{\frac{1}{2} n (n - 1)}$が出てくるのだろう。割愛。

話を戻し、$2^{\frac{n-1}{4}} det(L)^{\frac{1}{n}} < \frac{b^m}{\sqrt{n}}$をいい感じに変形すると（おそらく$n$のみの関数は無視？）、
\begin{align}
2^{\frac{n-1}{4}} det(L)^{\frac{1}{n}} &< \frac{b^m}{\sqrt{n}} \\
2^{\frac{n-1}{4}} (N^{\frac{1}{2} \delta m (m + 1)} X^{\frac{1}{2} n (n - 1)})^{\frac{1}{n}} &< \frac{N^{\beta m}}{\sqrt{n}} \\
N^{\frac{1}{2n} \delta m (m + 1)} X^{\frac{1}{2} (n - 1)} &< N^{\beta m} \\
N^{\frac{1}{n} \delta m (m + 1)} X^{(n-1)} &< N^{2 \beta m} \\
X^{(n-1)} &< N^{2 \beta m} N^{-\frac{1}{n} \delta m (m + 1)} \\
X &< N^{\frac{2 \beta m}{n-1} - \frac{\delta m (m + 1)}{n (n - 1)}}
\end{align}
⇩
$$X \leq \frac{1}{2} N^{\frac{2 \beta m}{n-1} - \frac{\delta m (m + 1)}{n (n - 1)}}$$ $n$の項を無視した分、余裕をもっている？

・ここからわからない（p13より）
$X^{n-1} < N^{\beta m}$
なにもの？
基底の最後の最高の単項式があーたこーだ書いてあるはず？
とすると、$h_i(x)$の最高次の話をしている？
$h_i(x) = x^i f^m(x) \quad ,(0 \leq i \leq t-1) \quad ②$
なので、$f(x)$の次数を$\delta$とすると、$f^m(x)$の次数は$\delta m$、$x^i$の次数は$t-1$であるので最高次は$\delta m + t - 1$となる。（$n \times n$行列で考えているのでそれは自明か。($n-1$）になることは自明。)
まとめると、最高次の単項式は$x^{n-1}$
$g(x)$から$g(xX)$にするので、最高次の係数は$X^{n-1}$になる。この時点で行列$L$の行列式が$N^{\beta m}$を超えるとお話にならないのでっていうことで条件をつけた？

\begin{align}
2^{\frac{n-1}{4}} det(L)^{\frac{1}{n}} &< \frac{b^m}{\sqrt{n}} \\
2^{\frac{n-1}{4}} (N^{\frac{1}{2} \delta m (m + 1)} X^{\frac{1}{2} n (n - 1)})^{\frac{1}{n}} < \frac{b^m}{\sqrt{n}} \\
\end{align}

$X = \frac{1}{2} N^{\frac{\beta^2}{\delta}-\epsilon}$を使うと書いてある。katagaitaiでのThm.6の式に似ている。
上の条件式を満たすと今まで行ってきた不等式を高い確率で満たせるのだろう。余裕を持ったパラメータ設定？

そのときのパラメーターは
$0 < \epsilon < \frac{1}{7} \beta$
$m = \frac{\beta^2}{\delta \epsilon}$のfloor
$t = \delta m (\frac{1}{\beta} - 1)$のfloor

よくわからないので

$$
\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
X\lt n^\frac{1}{n-1}\sqrt{2}X&\lt N^r\quad \left(r := \frac{2\beta m}{n-1}-\frac{\delta m(m+1)}{n(n-1)}\right)\cr
X\lt n^\frac{1}{n-1}\sqrt{2}X&\leq 2\sqrt{2}X\cr
\end{aligned}
$$

$1\lt \sqrt{2}$, $1\lt n^\frac{1}{n-1}$なので$1\lt n^{\frac{1}{n-1}}\sqrt{2}$.

$2\leq n$なので$n^\frac{1}{n-1}\leq 2$であり$n^{\frac{1}{n-1}}\sqrt{2}\leq 2\sqrt{2}$. $r := \frac{2\beta m}{n-1}-\frac{\delta m(m+1)}{n(n-1)}$として,

$$
\begin{aligned}
X&\lt \frac{1}{\sqrt{2}\cdot n^\frac{1}{n-1}}\cdot N^r\cr
&\lt \frac{1}{\sqrt{2}}N^r
\end{aligned}
$$

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

______

### 8/10(午前)

p.11の上の方でやっているのがおそらく以下。厳密にはdetは絶対値？
\begin{align}
2^{\frac{n-1}{4}} det(L)^{\frac{1}{n}} < \frac{N^m}{\sqrt{n}} \\
det(L)^{\frac{1}{n}} < 2^{-\frac{n-1}{4}} N^m n^{-\frac{1}{2}} \\
det(L) < 2^{-\frac{n(n-1)}{4}} N^{nm} n^{-\frac{n}{2}}
\end{align}

誤差項として小さい項を無視してシンプルに考えられる。
$$det(L) < N^{nm}$$ 以上を成り立つ限り$x_0$は効率よく求めることができるという***シンプルな条件***。p.12の上の方で$\beta$は$0 < \beta \leq 1$なので$$det(L) < N^{mn \beta}$$ これはシンプル化したものだが問題ない。

そして、p.12の下の方で$$det(L) = N^{\frac{1}{2} \delta m (m + 1)} X^{\frac{1}{2}n(n-1)}$$としている。ここから先ほど導出した問題ない式に代入して、
$$N^{\frac{1}{2} \delta m (m + 1)} X^{\frac{1}{2}n(n-1)} < N^{mn \beta}$$
両辺に$\frac{2}{n(n-1)}$乗して、左辺の$N$の項を移項すると、
$$X < N^{\frac{2 \beta m}{n-1}} N^{-\frac{\delta m (m+1)}{n(n-1)}}$$
$$X < N^{\frac{2 \beta m}{n-1} - \frac{\delta m (m+1)}{n(n-1)}}$$

これはシンプル化したものだが問題ない。$X$がこの不等式を満たしている限り$x_0$は効率よく求めることができる。

ここからなら$$X \leq \frac{1}{2}N^{\frac{2 \beta m}{n-1} - \frac{\delta m (m+1)}{n(n-1)}}$$が出てくることができる。
ここで、$<$が$\leq$に変化しているし、最初に誤差項を無視しているので適当に余裕をもって$X$を選択するために$\frac{1}{2}$をつけた？すくなくとも誤差項を$\frac{1}{2}$でカバーできるような記述は見つからなかった。