logo

半素数の素因数分解が容易に解ける条件 📂整数論

半素数の素因数分解が容易に解ける条件

要旨 1

準素数の素因数分解問題 $N = pq$ は、次の条件下では比較的簡単に解ける。

説明

条件 (ii) の意味は、$p$ と $q$ の差が少ないときに簡単に解けるということだが、これには説明が必要だろう：

  • 一見すると、$p,q \in \mathbb{N}$ が $(p + q)$ に制限されているなら、$N = pq$ を最大にする方法は、可能な限り $p$ と $q$ の差を小さくすることだ。例えば、$p+q \le 12$ であれば、$pq$ は $7 = p \approx q = 5$ のとき最大値 $35$ を持つ。

「力技で解く」ことを防ぐためには、$p$、$q$ は可能な限り大きい方がいい。例えば $$ N_{1}=3 \cdot 47=141 \\ N_{2}=11 \cdot 13=143 $$ があったとすると、公開された時には $2$ しか差がないが、$N_{1}$ は「手間をかけて」すぐに解けるようになる。

  • しかし、このような一次元的な理由で大きさが似ている $p$、$q$ を使う場合、二次元的に考える攻撃者には破られるしかない。単純に考えて、本当に $p \approx q$ なら攻撃者は $N \approx p^2$ と仮定し、$\sqrt{N}$ の近くにソリューションの候補を大幅に減らすことができる。このアイデアから数学的な技巧を駆使すれば、$N=pq$ は非常に簡単な問題になる。

証明

(i)

$p$ がスムーズな素数ならば、ポラード $p-1$ 素因数分解アルゴリズムを使うことができるので、準素数の素因数分解問題が比較的簡単に解けるようになる。

■

(ii)

$p := a + b$、$q := a - b$ とすると、$p$、$q$ は $a$ を中心に $\pm b$ 離れた素数になる。これを $N$ で表すと $$ \begin{align*} N =& ( a + b)(a - b) \\ =& a^2 - b^2 \end{align*} $$ つまり $N + b^2 = a^2$ となる。したがって、$N$ に $b$ を $1$ ずつ増やしながら $\left( N + b^2 \right)$ が平方数になるのを探すと $p = a + b$、$q = a - b$ が何であるかわかるので、準素数の素因数分解問題が比較的簡単に解ける。

■

例

例として、$N = 25217$ を考えよう。$N$ を直接素因数分解するのは容易ではないが、$25217 + 8^2 = 159^2$ とわかると $$ \begin{align*} p =& 159 + 8 = 167 \\ q =& 159-8 = 151 \end{align*} $$ をすぐに求めることができる。文の文脈に沿って言えば、$167 \approx 151$ のために簡単に解けてしまったのだ。

一方で、この $b$ を見つけるのをもっと賢くしよう。何か $k$ について $$ k N = a^2 - b^2 $$ とすると、$(a+b)$ と $(a-b)$ は $k$ の倍数なので、両辺を $k$ で割るだけで $N$ に関する式をそのまま得ることができる。このような面倒なことをする理由は、この式が次のように表せるからだ。 $$ a^2 \equiv b^2 \pmod{N} $$ その後は、次の方法で $d = q$ を探す。

ステップ 1. $c_{i}$

計算約数が少ない数 $c_{i}$ について、$c_{i} \equiv a_{i}^{2} \pmod{p}$ を満たす $a_{1} , \cdots , a_{r}$ を探しておく。

ステップ 2. $b^2$ の計算

$$ a_{i_{1}} \cdots a_{i_{s}} = a \\ c_{i_{1}} \cdots c_{i_{s}} = b^2 $$ を満たす $c_{i_{1}} , \cdots , c_{i_{s}}$ を探す。

ステップ 3. $d = \gcd \left( N , a-b \right)$

計算された $a$ と $b$ を用いて、 $$ \begin{align*} a^2 & \equiv \left( a_{i_{1}} \cdots a_{i_{s}} \right)^{2} \\ & \equiv a_{i_{1}}^{2} \cdots a_{i_{s}}^{2} \\ & \equiv c_{i_{1}} \cdots c_{i_{s}} \\ & \equiv b^2 \end{align*} $$ こうして $d$ は$N$ の約数、つまり $q$ になる。

参照

素因数分解問題の難しさを利用したセキュリティアルゴリズム

素因数分解問題に対する攻撃アルゴリズム

  1. Hoffstein. (2008). An Introduction to Mathematical Cryptography: p133~139. ↩︎