# coppersmith_3

### Lem.9の復習

***Lem.9***
$M$を法、$f(x)$を多項式とする。自然数$m,l$について
$$g_{i,j}(x) := M^{m-i}x^jf^i(x) \quad (0 \leq i \leq m,0 \leq j \leq l)$$とおく。このとき、$f(x_0) \equiv 0 \pmod M$をみたす$x_0$（整数）
について、$$g_{i,j}(x_0) \equiv 0 \pmod{M^m}$$が成り立つ。

与えられた条件
・$M$を法なので0より大きい整数
・$f(x)$は多項式
・$m,l$は0より大きい整数
・$g_{i,j}(x) := M^{m-i}x^jf^i(x) \quad (0 \leq i \leq m,0 \leq j \leq l)$
・$f(x_0) \equiv 0 \pmod M$をみたす$x_0$は整数

結論
・$g_{i,j}(x_0) \equiv 0 \pmod{M^m}$が成り立つ

***証明***
ある$k$が存在したとき、$f(x_0) = kM$と表すことができる（$kは整数$）。ゆえに$f^i(x_0) \equiv k^i M^i$となる。$g_{i,j}$の定義より$g_{i,j}(x_0) = M^{m-i}x_0^jf^i(x_0) = M^{m-i} x_0^jk^iM^i = k^ix_0^jM^m$
$k,x_0$は整数である。よって、
$$g_{i,j}(x_0) \equiv 0 \pmod{M^m}$$が成立する。
______

***Lem.13***
$b$を未知の法、$M$を既知の整数とし、$b$は$M$を割り切るとする。$f(x)$を多項式とし、自然数$m,l$について$$g_{i,j}(x) := M^{m-i}x^jf^i(x) \quad (0 \leq i \leq m,0 \leq j \leq l)$$とおく。このとき、$f(x_0) \equiv 0 \pmod{b}$を満たす$x_0$（整数）について、$$g_{i,j}(x_0) \equiv 0 \pmod{b^m}$$が成立する。

***Lem.9との違い***
・$b$を未知の法
・$M$は既知の整数
・$b|M$

***証明***
$t= \frac{M}{b}$とおく（$t,M,b$は整数）。
ある$整数k$が存在し、$f(x_0) = kb$である。ゆえに$f^i(x_0) = k^ib^i$である。Lem.9と同様に
$g_{i,j}(x_0) = M^{m-i}x_0^jf^i(x_0) = M^{m-i} x_0^jk^iM^i = (b \times t)^{m-i}x_0^jM^m　= t^{m-i}k^ix_0^jb^m$ゆえに
$$g_{i,j}(x_0) \equiv 0 \pmod{b^m}$$が成立する。

______

※そういえば、LLLの縮小ベクトルの定理については証明していなかったのですが、あれを証明しようとするとそれだけで一つの単元になるじゃないですか。。。今回はLLLは道具として使うので、証明は省略しても良いですか？？？（↓ちなみに個人的にわかりやすそうな資料）
https://mitsu1119.github.io/blog/post/post1/lll/

______

### 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| \leq N^{\frac{\beta^2}{\delta}}$$を満たす$x_0$を、効率よく求めることができる。

***与えられた条件***
・$N$を既知の整数
・$\beta$は$0 \leq \beta \leq 1$の実数
・$f(x)$はモニックな1変数$\delta$次多項式
・$b \geq N^\beta$、$b$は$N$の約数
・$x_0$は$f(x_0) \equiv 0 \pmod{b}$である・
・$|x_0| \leq N^{\frac{\beta^2}{\delta}}$である。

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

***証明***
Thm.4と同様に、$|x_0| \leq X$とおく（$X$は正の数）。Thm.4ではLem.9を使っていたところをLem.13にすることで、Howgrave-Graham’s LemmaとLLLの縮小ベクトルの定理の不等式は
$$X \leq b^{\frac{1}{\delta}}$$

\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}\\
X^{n-1} &\leq \left(\frac{1}{2}\right)^{\frac{n-1}{2}}\frac{M^m}{n}\\
X &\leq \left(\left(\frac{1}{2}\right)^{\frac{n-1}{2}}\frac{M^m}{n}\right)^{\frac{1}{n-1}}\\
X &\leq \frac{1}{\sqrt{2}}\left(\frac{M^m}{n}\right)^{\frac{1}{n-1}}\\
\end{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}}
$$

P.<x> = PolynomialRing(ZZ)

#f = x^2 + 87814262*x + 16117449
#M = 10007 * 10009
#X = 200

f = x + 248599182529905465437457958437694472192
M = 62769589329902986234605655823613674166084863265061735306358601544169662202263
X = 2^32
b = 870385989 + 248599182529905465437457958437694472192
beta = 0.45

m = 2
delta = f.degree(x) 
l = delta - 1

n = (m + 1) * (l + 1)

k = 0
B = matrix(n, n, 0)

#多項式の生成 & 係数行列化
for i in range(m + 1):
	for j in range(l + 1):
		gij = M^(m - i) * x^j * f^i
		for aaa in range(n):
			B[k, aaa] = gij.monomial_coefficient(x^aaa) * X^aaa
		k = k + 1

print(B)

left = 2^((n - 1) / 4) * B.det()^(1 / n)
print(2^((n - 1) / 4) * B.det()^(1 / n))

right = b^m / sqrt(n)
print(b^m / sqrt(n))
#right = M^m / sqrt(n)
#print(M^m / sqrt(n))


print(left <= right)

print(M^beta <= b)

print(X <= M^(beta^2 / delta))

となり、$X$がこの不等式を満たしているならば、$x_0$は効率よく求めることができる。

与えられた条件より、
\begin{align}
b &\geq N^\beta \\
N^\beta &\leq b \\
N^{\beta^2} &\leq b^\beta
\end{align}
$0 \leq \beta \leq 1$より$b^{\beta} \leq b$であるので、$$N^{\beta^2} \leq b$$ $$N^{\frac{\beta^2}{\delta}} \leq b^{\frac{1}{\delta}}$$（これは条件から導出したので常に成り立つ）
よって
$$X \leq N^{\frac{\beta^2}{\delta}}$$とすると、$X \leq b^{\frac{1}{\delta}}$を満たせるので$x_0$は効率よく求めることができると言い切れる。

***以上より言えること***

$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| \leq X$であり$X \leq N^{\frac{\beta^2}{\delta}}$、つまり
$$|x_0| \leq N^{\frac{\beta^2}{\delta}}$$を$x_0$が満たすならば、$x_0$は効率よく求めることができる。

以上より、Thm.6は証明できた。

------