共通のMSBを持つ素数を因数に持つ値の素因数分解

要するに

$N_1 = p_1q_1, N_2 = p_2q_2$ で $||N_1|| = ||N_2|| = n, ||q_1|| = ||q_2|| = \alpha$ 、 $p_1, p_2$ のMSB t-bitが共通のとき、素因数分解が可能

（ $t \ge 2\alpha + 3$ ）

$K = 2^{n-t}$ として、

$\vec{v_1} = (K, 0, N_2), \vec{v_2} = (0, K, -N_1)$

$B = (\vec{v_1} \vec{v_2})^T$

とすると、Bが張る格子Lの最小ベクトル $\vec{v_0}$ を求めることでいい感じになる。

$\vec{v_0} = q_1\vec{v_1} + q_2\vec{v_2}$ という線形結合で表され、

$\vec{v_0} = (q_1K, q_2K, q_1p_2q_2 - q_2p_1q_1) = (q_1K, q_2K, q_1q_2(p_2 - p_1))$

となる。

当然、 $q_1, q_2$ は不明なので線型結合で $\vec{v_0}$ を求めることは出来ないが、基底を構成すれば LLLによって $\vec{v_0}$ またはそれにほど近いベクトルが得られるので、 $q_1K$ などから $q_1$ が求まる。

TODO: v0が最小ベクトルとなることの証明

複数のNへの拡張

基底を次のようにとると、 $\vec{v_0} = (q_1K, q_2K, q_3K, ..., q_kK, hoge)$ が格子Lの最小ベクトルになる

[ [K, 0, 0, 0,    N2,  N3,  N4,     0,   0,   0],
  [0, K, 0, 0,   -N1,   0,   0,    N3,  N4,   0],
  [0, 0, K, 0,     0, -N1,   0,   -N2,   0,  N4],
  [0, 0, 0, K,     0,   0, -N1,     0, -N2, -N3]]

これがややこしければ、 $K = 2^{n-t}$ として

[ [K,  N2,  N3,  N4],
  [0, -N1,   0,   0],
  [0,   0, -N1,   0],
  [0,   0,   0, -N1]]

という基底を作ってLLLをすると、最小ベクトル $\vec{v_0} = (Kq_1, v_2, v_3, v_4)$ が得られる。ただし $v_i = (noise_i - noise_1)q_1q_i$ で、 $p_i = p + noise_i$

このページの出展は主にhttps://hal.archives-ouvertes.fr/hal-01288914/documentで、最後の小さい基底行列だけhttps://eprint.iacr.org/2014/548.pdf