半素数の素因数分解が容易に解ける条件
📂整数論 半素数の素因数分解が容易に解ける条件 要旨 準素数の素因数分解 問題 N = p q N = pq N = pq
(i): p p p スムーズな素数 である。 (ii): p ≈ q p \approx q p ≈ q 説明 条件 (ii) の意味は、p p p q q q
一見すると、p , q ∈ N p,q \in \mathbb{N} p , q ∈ N ( p + q ) (p + q) ( p + q ) N = p q N = pq N = pq p p p q q q p + q ≤ 12 p+q \le 12 p + q ≤ 12 p q pq pq 7 = p ≈ q = 5 7 = p \approx q = 5 7 = p ≈ q = 5 35 35 35 「力技で解く」ことを防ぐためには、p p p q q q N 1 = 3 ⋅ 47 = 141 N 2 = 11 ⋅ 13 = 143
N_{1}=3 \cdot 47=141
\\ N_{2}=11 \cdot 13=143
N 1 = 3 ⋅ 47 = 141 N 2 = 11 ⋅ 13 = 143 2 2 2 N 1 N_{1} N 1
しかし、このような一次元的な理由で大きさが似ている p p p q q q p ≈ q p \approx q p ≈ q N ≈ p 2 N \approx p^2 N ≈ p 2 N \sqrt{N} N N = p q N=pq N = pq 証明 (i) p p p スムーズな素数 ならば、ポラード p − 1 p-1 p − 1
■
(ii) p : = a + b p := a + b p := a + b q : = a − b q := a - b q := a − b p p p q q q a a a ± b \pm b ± b N N N N = ( a + b ) ( a − b ) = a 2 − b 2
\begin{align*}
N =& ( a + b)(a - b)
\\ =& a^2 - b^2
\end{align*}
N = = ( a + b ) ( a − b ) a 2 − b 2 N + b 2 = a 2 N + b^2 = a^2 N + b 2 = a 2 N N N b b b 1 1 1 ( N + b 2 ) \left( N + b^2 \right) ( N + b 2 ) p = a + b p = a + b p = a + b q = a − b q = a - b q = a − b
■
例 例として、N = 25217 N = 25217 N = 25217 N N N 25217 + 8 2 = 15 9 2 25217 + 8^2 = 159^2 25217 + 8 2 = 15 9 2 p = 159 + 8 = 167 q = 159 − 8 = 151
\begin{align*}
p =& 159 + 8 = 167
\\ q =& 159-8 = 151
\end{align*}
p = q = 159 + 8 = 167 159 − 8 = 151 167 ≈ 151 167 \approx 151 167 ≈ 151
一方で、この b b b k k k k N = a 2 − b 2
k N = a^2 - b^2
k N = a 2 − b 2 ( a + b ) (a+b) ( a + b ) ( a − b ) (a-b) ( a − b ) k k k k k k N N N a 2 ≡ b 2 ( m o d N )
a^2 \equiv b^2 \pmod{N}
a 2 ≡ b 2 ( mod N ) d = q d = q d = q
ステップ 1. c i c_{i} c i
計算約数が少ない数 c i c_{i} c i c i ≡ a i 2 ( m o d p ) c_{i} \equiv a_{i}^{2} \pmod{p} c i ≡ a i 2 ( mod p ) a 1 , ⋯ , a r a_{1} , \cdots , a_{r} a 1 , ⋯ , a r
ステップ 2. b 2 b^2 b 2
a i 1 ⋯ a i s = a c i 1 ⋯ c i s = b 2
a_{i_{1}} \cdots a_{i_{s}} = a
\\ c_{i_{1}} \cdots c_{i_{s}} = b^2
a i 1 ⋯ a i s = a c i 1 ⋯ c i s = b 2 c i 1 , ⋯ , c i s c_{i_{1}} , \cdots , c_{i_{s}} c i 1 , ⋯ , c i s
ステップ 3. d = gcd ( N , a − b ) d = \gcd \left( N , a-b \right) d = g cd( N , a − b )
計算された a a a b b b a 2 ≡ ( a i 1 ⋯ a i s ) 2 ≡ a i 1 2 ⋯ a i s 2 ≡ c i 1 ⋯ c i s ≡ b 2
\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*}
a 2 ≡ ( a i 1 ⋯ a i s ) 2 ≡ a i 1 2 ⋯ a i s 2 ≡ c i 1 ⋯ c i s ≡ b 2 d d d N N N 約数 、つまり q q q
参照 素因数分解問題の難しさを利用したセキュリティアルゴリズム 素因数分解問題に対する攻撃アルゴリズム 