素因數分解 ( 英語 : prime factorization, integer factorization )는 1보다 큰 自然數를 素因數( 少數 人 引受 )들만의 곱으로 나타내는 것 또는 合成數 를 少數 의 곱으로 나타내는 方法을 말한다. 素因數分解를 一義的으로 決定하는 公式은 아직 發見되지 않았다. 現代 暗號 處理에서 素因數分解의 어려움은 重要한 基準이 된다.

槪要 [ 編輯 ]

算術의 基本 整理 (fundamental theorem of arithmetic)에 依해 모든 陽의 正數는 少數들의 곱으로 表現하는 方法이 (곱셈의 交換法則 을 除外하면) 唯一하게 存在한다. 그러나 算術의 基本整理는 그 素因數分解를 하는 方法을 알려주지는 않는다. 但只 存在性을 確認해 줄 뿐이다.

아래는 200 以下 合成數 의 素因數分解이다. ^[1]

• 4＝2×2(2 ² )
• 6＝2×3
• 8＝2×2×2(2 ³ )
• 9＝3×3(3 ² )
• 10＝2×5
• 12＝2×2×3(2 ² x3)
• 14＝2×7
• 15＝3×5
• 16＝2×2×2×2(2 ⁴ )
• 18＝2×3×3(2x3 ² )
• 20＝2×2×5(2 ² x5)
• 21＝3×7
• 22＝2×11
• 24＝2×2×2×3(2 ³ x3)
• 25＝5×5(5 ² )
• 26＝2×13
• 27＝3×3×3(3 ³ )
• 28＝2×2×7(2 ² x7)
• 30＝2×3×5
• 32＝2×2×2×2×2(2 ⁵ )
• 33＝3×11
• 34＝2×17
• 35＝5×7
• 36＝2×2×3×3(2 ² x3 ² )
• 38＝2×19
• 39＝3×13
• 40＝2×2×2×5(2 ³ x5)
• 42＝2×3×7
• 44＝2×2×11
• 45＝3×3×5(3 ² x5)
• 46＝2×23
• 48＝2×2×2×2×3(2 ⁴ x3)
• 49＝7×7(7 ² )
• 50＝2×5×5(2x5 ² )
• 51＝3×17
• 52＝2×2×13(2 ² x13)
• 54＝2×3×3×3(2x3 ³ )
• 55＝5×11
• 56＝2×2×2×7(2 ³ x7)
• 57＝3×19
• 58＝2×29
• 60＝2×2×3×5(2 ² x3x5)
• 62＝2×31
• 63＝3×3×7(3 ² x7)
• 64＝2×2×2×2×2×2(2 ⁶ )
• 65＝5×13
• 66＝2×3×11
• 68＝2×2×17(2 ² x17)
• 69＝3×23
• 70＝2×5×7
• 72＝2×2×2×3×3(2 ³ x3 ² )
• 74＝2×37
• 75＝3×5×5(3x5 ² )
• 76＝2×2×19(2 ² x19)
• 77＝7×11
• 78＝2×3×13
• 80＝2×2×2×2×5(2 ⁴ x5)
• 81＝3×3×3×3(3 ⁴ )
• 82＝2×41
• 84＝2×2×3×7(2 ² x3x7)
• 85＝5×17
• 86＝2×43
• 87＝3×29
• 88＝2×2×2×11(2 ³ x11)
• 90＝2×3×3×5(2x3 ² x5)
• 91＝7×13
• 92＝2×2×23(2 ² x23)
• 93＝3×31
• 94＝2×47
• 95＝5×19
• 96＝2×2×2×2×2×3(2 ⁵ x3)
• 98＝2×7×7(2x7 ² )
• 99＝3×3×11(3 ² x11)
• 100＝2×2×5×5(2 ² x5 ² )
• 102＝2×3×17
• 104＝2×2×2×13(2 ³ x13)
• 105＝3×5×7
• 106＝2×53
• 108＝2×2×3×3×3(2 ² x3 ³ )
• 110＝2×5×11
• 111＝3×37
• 112＝2×2×2×2×7(2 ⁴ x7)
• 114＝2×3×19
• 115＝5×23
• 116＝2×2×29(2 ² x29)
• 117＝3×3×13(3 ² x13)
• 118＝2×59
• 119＝7×17
• 120＝2×2×2×3×5(2 ³ x3x5)
• 121＝11×11(11 ² )
• 122＝2×61
• 123＝3×41
• 124＝2×2×31(2 ² x31)
• 125＝5×5×5(5 ³ )
• 126＝2×3×3×7(2x3 ² x7)
• 128＝2×2×2×2×2×2×2(2 ⁷ )
• 129＝3×43
• 130＝2×5×13
• 132＝2×2×3×11(2 ² x3x11)
• 133＝7×19
• 134＝2×67
• 135＝3×3×3×5(3 ³ x5)
• 136＝2×2×2×17(2 ³ x17)
• 138＝2×3×23
• 140＝2×2×5×7(2 ² x5x7)
• 141＝3×47
• 142＝2×71
• 143＝11×13
• 144＝2×2×2×2×3×3(2 ⁴ x3 ² )
• 145＝5×29
• 146＝2×73
• 147＝3×7×7(3x7 ² )
• 148＝2×2×37(2 ² x37)
• 150＝2×3×5×5(2x3x5 ² )
• 152＝2×2×2×19(2 ³ x19)
• 153＝3×3×17(3 ² x17)
• 154＝2×7×11
• 155＝5×31
• 156＝2×2×3×13(2 ² x3x13)
• 158＝2×79
• 159＝3×53
• 160＝2×2×2×2×2×5(2 ⁵ x5)
• 161＝7×23
• 162＝2×3×3×3×3(2x3 ⁴ )
• 164＝2×2×41(2 ² x41)
• 165＝3×5×11
• 166＝2×83
• 168＝2×2×2×3×7(2 ³ x3x7)
• 169＝13×13(13 ² )
• 170＝2×5×17
• 171＝3×3×19(3 ² x19)
• 172＝2×2×43(2 ² x43)
• 174＝2×3×29
• 175＝5×5×7(5 ² x7)
• 176＝2×2×2×2×11(2 ⁴ x11)
• 177＝3×59
• 178＝2×89
• 180＝2×2×3×3×5(2 ² x3 ² )
• 182＝2×7×13
• 183＝3×61
• 184＝2×2×2×23(2 ³ x23)
• 185＝5×37
• 186＝2×3×31
• 187＝11×17
• 188＝2×2×47(2 ² x47)
• 189＝3×3×3×7(3 ³ x7)
• 190＝2×5×19
• 192＝2×2×2×2×2×2×3(2 ⁶ x3)
• 194＝2×97
• 195＝3×5×13
• 196＝2×2×7×7(2 ² x7 ² )
• 198＝2×3×3×11(2x3 ² x11)
• 200＝2×2×2×5×5(2 ³ x5 ² )

素因數分解 알고리즘 [ 編輯 ]

現代의 電磁氣 基盤 컴퓨터上에서 素因數分解에 對한 多項式 時間 알고리즘 은 알려져 있지 않다. 單, 理論的인 量子컴퓨터 에서의 多項式 時間 素因數分解 알고리즘 ( 쇼어의 알고리즘 )은 存在한다. 하지만 아직까지 어떤 合成數를 다항 時間 안에 素因數分解하기는 어려운 問題이며, 例를 들어 193자리 數(RSA-640)는 5個月間 30個의 2.2 GHz 옵테론 CPU를 動員하여 素因數分解 되었다. 素因數分解의 難解함은 RSA 와 같은 現代 暗號의 核心的 部分이 된다.

古典的 알고리즘 [ 編輯 ]

古典的인 素因數分解 알고리즘은 大部分 페르마 小定理 를 擴張한 것을 利用한다. 그中 자주 使用되는 알고리즘은 아래와 같다.

• 윌리엄의 p+1 알고리즘
• 폴라드의 p-1 알고리즘
• 폴라드 로 알고리즘
• 페르마의 알고리즘

알고리즘의 發展 [ 編輯 ]

暗號學 의 發達과 함께 素因數分解 方法도 發展해 왔으며 그中 가장 效率的인 알고리즘들을 간추리면 아래와 같다.

• 렌스트라의 楕圓曲線 알고리즘 (Elliptic Curve Method, ECM): 楕圓曲線의 性質을 利用하여 어떤 數를 素因數分解하는 알고리즘으로, 가장 작은 素因數의 크기에 따라서 實行 時間이 決定된다. 이 알고리즘의 實行 時間은 ${\displaystyle O\left(\exp \left({\sqrt {2\ln(p\ln(\ln(p))}}\right)\right)}$로 以前의 剩餘體 의 性質을 利用한 알고리즘에 비해 매우 優秀하다.
• 수체 체 (General Number Field Sieve, GNFS) 알고리즘은 二次 체 알고리즘을 발전시킨 것으로 一般 컴퓨터로 實行시킬 수 있는 알고리즘 中에서는 가장 빠른 알고리즘이다. b가 合成數의 비트數日 때, 이 알고리즘은 ${\displaystyle O\left(\exp \left(\left({\begin{matrix}{\frac {64}{9}}\end{matrix}}b\right)^{1 \over 3}(\log b)^{2 \over 3}\right)\right)}$의 時間複雜度를 가진다.
• 特需 수체 체 (Special Number Field Sieve, SNFS) 알고리즘은 r, e, s가 自然數일 때, r ^e ± s 꼴인 自然數에 對해서 作動하는 알고리즘이다. 여기서 r, s의 값이 커지면 速度가 急速度로 느려지기 때문에 r, s가 작은 自然數에 對해서만 잘 作動하며 使用할 수 있다.
• 多重 多項式 이車體 (Multiple Polynomial Quadratic Sieve, MPQS) 알고리즘은 二次 체 알고리즘을 擴張시킨 알고리즘으로, 한 個의 函數를 利用하는 二次 體와는 달리 여러 個의 函數를 利用하는 알고리즘이다.
• 二次 체 (Quadratic Sieve, QS) 알고리즘은 100자리 以下의 自然數를 素因數分解할 때 適合하며, 普通 어떤 合成數의 素因數들의 크기가 비슷할 때 잘 作動한다.

같이 보기 [ 編輯 ]

위키미디어 共用 에 關聯된
미디어 分類가 있습니다.

素因數分解

數學 포털

• 藥水
• 合成數
• 因數 分解
  • 곱셈 公式
• 整數論의 基本 整理 (fundamental theorem of arithmetic)
• RSA 暗號
• 時間 複雜度
• 漸近 表記法

各州 [ 編輯 ]