# SecCamp成果物
### Howgrave-Graham's Lemma
$M^m$を法、$g(x)$を$\delta$次整数多項式とし、含まれる単項式の次数を$\omega$とする。$g(x)$に対してある$X$が存在し、$g(x_0) \equiv 0 \pmod{M^m}$なる$x_0$について、$|x_0| \leq X$であると仮定する。このとき、
$$||g(xX)|| < \frac{M^m}{\sqrt{\omega}}$$
が成立するならば、$g(x_0)=0$が成立する。
⇒moduler方程式を整数方程式に変換できる。
証明
仮定$||g(xX)|| < \frac{M^m}{\sqrt{\omega}}$を式変形し、
\begin{align}
|g(x_0)| &= |\sum_{i=0}^{\delta}{g_i x_0^i}| \\
&\leq \sum_i{|g_i x_0^i|} \\
&\leq \sum_i{|g_i| X^i}
\end{align}
Cauchy-Schwarzの不等式の変形$\sum_i x_iy_i \leq \sqrt{(\sum_i x_i^2)\sqrt{(\sum_i y_i^2)}}$を用いて
\begin{align}
\sum_i{|g_i| X^i} &= \sum_i{(1 \cdot |g_i|)} \\
&\leq \sqrt{\sum_{i=0,g_i \neq 0}{1}} \sqrt{\sum_i{(|g_i|X^i)^2}} \\
\end{align}
$g_i \neq 0$な$g_i$の個数は$\omega$なので
$$\sqrt{\sum_{i=0,g_i \neq 0}{1}} \sqrt{\sum_i{(|g_i|X^i)^2} = \sqrt{\omega}} ||g(xX)|| < M$$
$g(x_0) \equiv 0 \pmod{M}$よりある整数$k$が存在して$g(x_0) = kM$と表せる。この$k$は
$||g(xX)|| < M$であり、$||g(x_0)|| < ||g(xX)||$であるので、明らかに0である。よって$g(x_0) = 0$が成立することを意味している。
---
### Thm.4の証明（１）
$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$）。
katagaitaiでのLem.9+David Wongの論文より、パラメータ$m,t$を設定する。これは条件式により導出できるがヒューリスティック的に選択することが実用的であるだろう。
法$N^m$上で$x_0$と同じ解を持つ方程式を大量に生成する。
---
***Lem.9***
$M$を法、$f(x)$を$\delta$次多項式とする。自然数$m$について
$$g_{i,j}(x) := M^{m-i}x^jf^i(x) \quad (0 \leq i \leq m-1,0 \leq j \leq \delta-1)$$とおく。このとき、$f(x_0) \equiv 0 \pmod M$をみたす$x_0$（整数）
について、
$$g_{i,j}(x_0) \equiv 0 \pmod{M^m}$$が成り立つ。
与えられた条件
・$M$を法なので0より大きい整数
・$f(x)$は多項式
・$m$は0より大きい整数
・$g_{i,j}(x) := M^{m-i}x^jf^i(x) \quad (0 \leq i \leq m-1,0 \leq j \leq \delta-1)$
・$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) = k^i M^i$となる。$g_{i,j}(x)$の定義より$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}$$が成立する。
このとき生成される方程式の数は$\delta m$個である。
***David Wongの定理***
$M$を法、$f(x)$を多項式とする。自然数$m,t$について、
$$h_i := x^i f^m(x)$$とおく。このとき、$f(x_0) \equiv 0 \pmod{M}$を満たす$x_0$について、$h_i(x_0) \equiv 0 \pmod{M^m}$を満たす。
証明
ある$k$が存在したとき、$f(x_0) = kM$と表すことができる。ゆえに$f^m(x_0) = k^m M^m$となる。$h_i$の定義より、$h_i(x_0) = x_0^ik^mM^m$なので$h_i(x_0) \equiv 0 \pmod{M^m}$
このとき生成される方程式の数は$t$個である。
---
### Thm.4の証明（２）
ここで生成した方程式から$g_{i,j}(x),h_i(x)$から$g_{i,j}(xX),h_i(xX)$による係数行列を構成する。生成される方程式の数は合計で$\delta m + t$個であり、生成される方程式の項数も$\delta m + t$個である。$n := \delta m + t$とすると構成する係数行列$B$は$n \times n$行列である。このとき係数の並べ方に特殊な条件（生成される方程式の次数が低いものから順番にならべ、列数と方程式の各項の次数を対応づけて並べる→対角成分に各方程式の最高次数が並んだ下三角行列）をつけると、行列$B$の行列式$det(B)$は
$$det(B) = N^{\frac{1}{2} \delta m (m+1)}X^{\frac{1}{2}n(n-1)}$$と表せることができる。
係数の並べ方に条件を付けない一般の行列$B'$に対して、行と列の基本変形より$|\mathrm{det}(B')| = |\mathrm{det}(B)|$である。ゆえに
$$|\mathrm{det} (B')| = |\mathrm{det} (B)| = |N^{\frac{1}{2} \delta m (m+1)}X^{\frac{1}{2}n(n-1)}|$$ $N,X$は正の数であるから
$$|\mathrm{det} (B')| = |\mathrm{det} (B)| = N^{\frac{1}{2} \delta m (m+1)}X^{\frac{1}{2}n(n-1)}$$であるので、一般の行列$B'$においても議論ができる。
この行列$B$をLLLして出力されるベクトル（方程式の係数なので方程式と言い換えても良い）$b_1'(xX)$は、$g_{i,j}(xX),h_i(xX)$と法$N^m$上で同じ解を持っていて（※）、$b_1'(xX)$の各次数の項を$X^{z},(0 \leq z \leq n-1)$で割った方程式$b_1'(x)$は方程式$g_{i,j}(x),h_i(x)$と同じ根を持っている。つまり与えられた方程式$f(x)$と同じ解を持っている。よってLLLにより出力される方程式$b_1'(xX)$について$$||b_1'(xX)|| < \frac{N^m}{\sqrt{n}}$$が成立したとき$b_1'(x) \equiv 0 \pmod{N^m}$は$b_1'(x) = 0$が成立する
$b_1'(xX)$はLLLのノルムの条件で評価できるので、
\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}$$$$|det(L)|^{\frac{1}{n}} < N^{m}$$行列式を当てはめ
\begin{align}
(N^{\frac{1}{2} \delta m (m+1)}X^{\frac{1}{2}n(n-1)})^{\frac{1}{n}} &< N^{m} \\
N^{\frac{1}{2n} \delta m (m+1)}X^{\frac{n-1}{2}} &< N^{m} \\
N^{\frac{\delta m (m+1)}{n(n-1)}} X &< N^{\frac{2m}{n-1}} \\
X &< N^{-\frac{\delta m (m+1)}{n(n-1)}} N^{\frac{2m}{n-1}} \\
X &< N^{-\frac{\delta m (m+1)}{n(n-1)}} N^{\frac{2m}{n-1}} N^{\frac{1}{\delta}} N^{-\frac{1}{\delta}} \\
X &< N^{\frac{2m}{n-1}} N^{-\frac{\delta m (m+1)}{n(n-1)}} N^{\frac{1}{\delta}} N^{-\frac{1}{\delta}} \\
X &< N^{\frac{2mn}{n(n-1)}} N^{-\frac{\delta m (m+1)}{n(n-1)}} N^{-\frac{1}{\delta}} N^{\frac{1}{\delta}} \\
X &< N^{\frac{2m(\delta m + t)}{n(n-1)}} N^{-\frac{\delta m (m+1)}{n(n-1)}} N^{-\frac{1}{\delta}} N^{\frac{1}{\delta}} \\
X &< N^{\frac{2\delta m^2 + 2mt}{n(n-1)}} N^{-\frac{\delta m^2 + \delta m}{n(n-1)}} N^{-\frac{1}{\delta}} N^{\frac{1}{\delta}} \\
X &< N^{\frac{2\delta m^2 + 2mt -\delta m^2 -\delta m}{n(n-1)}} N^{-\frac{1}{\delta}} N^{\frac{1}{\delta}} \\
X &< N^{\frac{\delta m^2 + 2mt -\delta m}{n(n-1)}} N^{-\frac{1}{\delta}} N^{\frac{1}{\delta}} \\
X &< N^{\frac{\delta m^2 + 2mt -\delta m}{n(n-1)}} N^{-\frac{n(n-1)}{\delta n (n-1)}} N^{\frac{1}{\delta}} \\
X &< N^{\frac{\delta m^2 + 2mt -\delta m}{n(n-1)}} N^{-\frac{(\delta m + t)(\delta m + t -1)}{\delta n (n-1)}} N^{\frac{1}{\delta}} \\
X &< N^{\frac{\delta m^2 + 2mt -\delta m}{n(n-1)}} N^{-\frac{\delta ^2 m^2 + \delta m t -\delta m + \delta m t + t^2 - t}{\delta n (n-1)}} N^{\frac{1}{\delta}} \\
X &< N^{\frac{\delta^2 m^2 + 2\delta m t -\delta^2 m}{\delta n(n-1)}} N^{-\frac{\delta ^2 m^2 + \delta m t -\delta m + \delta m t + t^2 - t}{\delta n (n-1)}} N^{\frac{1}{\delta}} \\
X &< N^{\frac{\delta^2 m^2 + 2\delta m t -\delta^2 m -\delta^2 m^2 -\delta mt + \delta m -\delta m t -t^2 + t} {\delta n(n-1)}} \quad N^{\frac{1}{\delta}} \\
X &< N^{\frac{-\delta^2 m + \delta m -t^2 + t} {\delta n(n-1)}} \quad N^{\frac{1}{\delta}} \\
X &< N^{\frac{-\delta^2 m + \delta m -t^2 + t} {\delta n(n-1)}} \quad N^{\frac{1}{\delta}} \\
X &< N^{\frac{-\delta^2 m -t^2 + n} {\delta n(n-1)}} \quad N^{\frac{1}{\delta}} \\
N^{\frac{\delta^2 m + t^2 - n} {\delta n(n-1)}} X &< N^{\frac{1}{\delta}} \\
\end{align}
以上の式を満たしている限り、$x_0$は効率よく求めることができる。
ここで$\epsilon = \frac{\delta^2 m + t^2 - n} {\delta n(n-1)}$とすると、
$$X \leq N^{\frac{1}{\delta} - \epsilon}$$
となる、パラメータ$m,t$を十分大きくした場合$\epsilon$は極めて小さくなるので
$$X \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$）。このとき、$X \leq N^{\frac{1}{\delta}}$であれば$x_0$を効率よく求めることができる。ゆえに、
$$|x_0| \leq N^{\frac{}{}}$$であるとき、$x_0$は効率よく求めることができる。
---
### ※の証明
$M$を法、$f(x) \equiv 0 \pmod{M},g(x) \equiv 0 \pmod{M}$を同じ解$x_0$を持つようなmoduler方程式とする。このとき、任意の整数$a,b$について $$af(x) + bf(x) \equiv 0 \pmod{M}$$を解にもつ。
証明
$$af(x_0) + bg(x_0) \equiv a \cdot 0 + b \cdot 0 \equiv 0 \pmod{M}$$
---
### 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$は効率よく求めることができる。
---
***Lem.13***
$b$を未知の法、$M$を既知の整数とし、$b$は$M$を割り切るとする。$f(x)$を$\delta$次多項式とし、自然数$m,l$について$$g_{i,j}(x) := M^{m-i}x^jf^i(x) \quad (0 \leq i \leq m-1,0 \leq j \leq \delta - 1)$$とおく。このとき、$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}$$が成立する。
---
### Thm.6の証明（２）
Thm.6ではThm.4でのLem.9をLem.13に置き換えたものであるので、
$$(N^{\frac{1}{2} \delta m (m+1)}X^{\frac{1}{2}n(n-1)})^{\frac{1}{n}} < b^{m}$$
この不等式が成り立つとき$x_0$は効率よく求めることができる。
$N^\beta < b$であるので、$(N^{\frac{1}{2} \delta m (m+1)}X^{\frac{1}{2}n(n-1)})^{\frac{1}{n}} < N^{\beta m}$が示せれば十分。
\begin{align}
N^\frac{\delta m(m + 1)}{n(n-1)} X&\lt N^{\beta\frac{2m}{n-1}}\cr
X &\lt N^{\beta\frac{2m}{n-1}-\frac{\delta m(m + 1)}{n(n-1)}}N^{-\frac{\beta^2}{\delta}}N^{\frac{\beta^2}{\delta}} \\
\end{align}
このとき右辺の指数をまとめると、
$$
\begin{aligned}
\beta\frac{2m}{n-1}-\frac{\delta m(m + 1)}{n(n-1)} - \frac{\beta^2}{\delta} + \frac{\beta ^ 2}{\delta} &= \frac{2\beta\delta mn - \delta^2 m(m+1) - n\beta^2(n-1)}{\delta n(n-1)} + \frac{\beta ^ 2}{\delta}
\end{aligned}
$$
となる。$\epsilon = \frac{2\beta\delta mn - \delta^2 m(m+1) - n\beta^2(n-1)}{\delta n(n-1)}$とすると
$$X \leq N^{\frac{\beta^2}{\delta} + \epsilon}$$となるが、誤差項$\epsilon$は極めて小さくなるので、無視して考えてよい。よって$$X \leq N^{\frac{\beta^2}{\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は証明できた。
---
### （緑川先生導出）
* $N^r X \lt b^s$が成り立つような変形をしたい
* $N^{\beta s}\leq b^s$は成立する
* $N^r X \lt N^{\beta s}$が成立しているならば, $N^r X\lt b^s$も成立する
* $X\lt N^{\beta s - r}$
- $\beta s - r$がなんかこんな簡単な形で書けます, というのが言えればよいo
$$
\begin{aligned}
N^\frac{\delta m(m + 1)}{n(n-1)} X&\lt N^{\beta\frac{2m}{n-1}}\cr
X &\lt N^{\beta\frac{2m}{n-1}-\frac{\delta m(m + 1)}{n(n-1)}}N^{-\frac{\beta^2}{\delta}}N^{\frac{\beta^2}{\delta}}
\end{aligned}
$$
$$
\begin{aligned}
\beta\frac{2m}{n-1}-\frac{\delta m(m + 1)}{n(n-1)} - \frac{\beta^2}{\delta} &= \frac{2\beta\delta mn - \delta^2 m(m+1) - n\beta^2(n-1)}{\delta n(n-1)}
\end{aligned}
$$
```
? f(b,d,m,t)=n=d*m+t;(d*m*(2*b*n-d*(m+1))-b^2*n*(n-1))/(d*n*(n-1))
%47 = (b,d,m,t)->n=d*m+t;(d*m*(2*b*n-d*(m+1))-b^2*n*(n-1))/(d*n*(n-1))
? f(1, 2, 4, 2) * 1.0
%48 = -0.055555555555555555555555555555555555556
? f(1, 2, 6, 2) * 1.0
%49 = -0.038461538461538461538461538461538461539
? f(0.5, 2, 6, 2) * 1.0
%50 = -0.12500000000000000000000000000000000000
? f(0.25, 2, 6, 2) * 1.0
%51 = -0.26201923076923076923076923076923076923
? f(0.25, 2, 6, 4) * 1.0
%52 = -0.18125000000000000000000000000000000000
? f(1, 2, 6, 4)
%54 = -1/20
```
---
### 実装
入力：
・多項式$f(x)$
・既知の整数$M$
・パラメータ$\beta$
・$\beta$と$N$より設定される解の上界$X$
・ヒューリスティックなパラメータ$m,t$
出力：
・未知の法$b$で$f(x_0) \equiv 0 \pmod{b}$を満たす解$x_0$
***パラメータ***
Thm.6に基づき設定されている。
・$f(x) = x^2 + 773846814961772893618287x + 929672459026049085166630$
・$N = 10007^{10} \times 9973$
・$\beta = 0.5$
・$X = 300$，$|x_0| \leq X$であると決め打つ。
・$m = 4,t = 4$
・実際の解は
$$f(x_0) \equiv 0 \pmod{b=10007^{6}}$$において$x_0 =222,1234567898765432123456789$
***コード***
```python
P.<x> = PolynomialRing(ZZ)
f = x^2 + 773846814961772893618287*x + 929672459026049085166630
M = 10007^10 * 9973
#b = 10007^6
X = 300
beta = 0.5
delta = f.degree(x)
m = 4
t = 4
#tが2まで落ちると解がでない
n = m * delta + t
k = 0
B = matrix(n, n, 0)
#多項式の生成 & 係数行列化
for i in range(m):
for j in range(delta):
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
for i in range(t):
hi = x^i * f^m
for aaa in range(n):
B[k, aaa] = hi.monomial_coefficient(x^aaa) * X^aaa
k = k + 1
rB = B.LLL()
for aaa in range(n):
bn = rB[aaa]
z = 0
for bbb in range(n):
z = z + (bn[bbb] / X^bbb) * x^bbb
kai = z.roots()
if(len(kai) != 0):
for ccc in range(delta):
test = kai[0][ccc]
#条件を満たすか判定
fff = 0
print("判定する解:",test)
b = gcd(M,f.subs(x=test))
print("未知の法b=",b)
if(M^beta <= b):
print("M^β <= bを満たします")
fff = fff + 1
if(abs(test) <= M^(beta^2 / delta)):
print("|x_0| <= M^(β^2/δ)を満たします")
fff = fff + 1
if(X <= M^(beta^2 / delta)):
print("X <= M^(β^2/δ)を満たします")
fff = fff + 1
if(fff == 3):
print("以上より、次の解は適切です")
print("解x_0=",test)
exit()
else:
print("条件を満たしません")
```
***出力***
```
判定する解: 222
未知の法b= 1004207356863602508537649
M^β <= bを満たします
|x_0| <= M^(β^2/δ)を満たします
X <= M^(β^2/δ)を満たします
以上より、次の解は適切です
解x_0= 222
```
---
Sign in with Wallet
Connect another wallet