# Thm.6のアルゴリズム起こし

### パラメータ設定（メモ書き）
$N = 293^4 \times 307 = 2262605595907$
$b = 293^4 = 7370050801$
$f'(x):=(x-222)(x-12345)(x-98765)$
$f'(x):=x^3 - 111332 x^2 + 1243920345 x - 270674371350$
$\delta = 3$
$\beta =0.78$
$N^{\beta} = 4331067062$
$b \geq N^\beta,b|N$
$N^{\frac{\beta^2}{\delta}} \approx 320.268832172320$

$f'(x) = 0$なる$f'(x) = (k'b+a_3)x^3 + (k'b+a_2)x^2 + (k'b+a_1)x + a_0$があったとき、$f(x) \equiv 0 \pmod{b}$は$f'(x)$の各項の$\pmod{b}$をとれば良い。

$f(x) := x^3 + 7369939469 x^2 + 1243920345 x + 2017508287$
$f(x) \equiv 0 \pmod{b}$

$b \geq N^\beta,b|N$

$X \leq b^{\frac{1}{\delta}}$

以上のパラメータで問題ないか確かめる。
・コード

P.<x> = PolynomialRing(ZZ)

N = 293^4 * 307
print("法N:")
print(N)

b = 293^4
print("Nの約数である未知数b:")
print(b)

fd = (x-222)*(x-12345)*(x-98765)
print("解にx=222,12345,98765をもつ通常の多項式f'(x)")
print(fd)

f = x^3 + 7369939469 * x^2 + 1243920345 * x + 2017508287
print("f'(x)の各項をbで割った余りの式f(x)")
print(f)

print("f(x)はf(x)≡ 0 (mod b)(x = 222,12345,98765)をもつはず")
print("以下はそれぞれf(x)にx=222,12345,98765に代入してbで剰余をとった値")
print((222^3 + 7369939469 * 222^2 + 1243920345 * 222 + 2017508287) % b)
print((12345^3 + 7369939469 * 12345^2 + 1243920345 * 12345 + 2017508287) % b)
print((98765^3 + 7369939469 * 98765^2 + 1243920345 * 98765 + 2017508287) % b)

beta = 0.78
print("実数β:")
print(beta)

delta = f.degree(x)
print("f(x)の次数δ:")
print(delta)

print("条件N^β")
print(int(N^beta))

print("条件N^(β^2 / δ)")
print(int(N^(beta^2 / delta)))

・出力

法N:
2262605595907
Nの約数である未知数b:
7370050801
解にx=222,12345,98765をもつ通常の多項式f'(x)
x^3 - 111332*x^2 + 1243920345*x - 270674371350
f'(x)の各項をbで割った余りの式f(x)
x^3 + 7369939469*x^2 + 1243920345*x + 2017508287
f(x)はf(x)≡ 0 (mod b)(x = 222,12345,98765)をもつはず
以下はそれぞれf(x)にx=222,12345,98765に代入してbで剰余をとった値
0
0
0
実数β:
0.780000000000000
f(x)の次数δ:
3
条件N^β
4331067062
条件N^(β^2 / δ)
320

以上をThm.6に当てはめる。

$N$を既知の整数($2262605595907$)、$0 \leq \beta \leq 1$を実数とし($0.78$)、$f(x)$をモニックな1変数$\delta$次多項式
($x^3 + 7369939469*x^2 + 1243920345*x + 2017508287,\delta = 3$)
とする。このとき、未知の$b \geq N^\beta,b|N$
($7370050801 \geq 4331067062$)について$f(x_0) \equiv 0 \pmod{b}$が成立（先ほど確かめた）、かつ
$$|x_0| \leq N^{\frac{\beta^2}{\delta}}$$を満たす$x_0$を、効率よく求めることができる。
（解$x_0$は$222$,$N^{\frac{\beta^2}{\delta}} \approx 320$）

よってこのパラメータでやっていけばいいはず。

### ダメだったのでパターン2
$N = 293^4 \times 307 = 2262605595907$
$b = 293^4 = 7370050801$
$f'(x):=(x-222)(x-12345)(x-98765)$
$f'(x):=x^3 - 111332 x^2 + 1243920345 x - 270674371350$
$\delta = 3$
$\beta =0.78$
$N^{\beta} = 4331067062$
$b \geq N^\beta,b|N$
$N^{\frac{\beta^2}{\delta}} \approx 320.268832172320$