---
# System prepended metadata

title: SecCamp成果物

---

# 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
```



---
