素因数分解
素因数分解 (そいんすうぶんかい、英: prime factorization) とは、ある正の整数を素数の積の形で表すことである。ただし、1 に対する素因数分解は 1 と定義する[注 1]。
素因数分解には次のような性質がある。
インターネットでの認証等で利用されている公開鍵暗号の代表であるRSA暗号の安全性は、巨大な合成数の素因数分解を実用的な時間内に実行することが困難であることと深い関わりがあり、RSA 以外の公開鍵暗号でも素因数分解問題に基づく方式が多々あるため、素因数分解のアルゴリズムが活発に研究されている。また実際に巨大な合成数の素因数分解の計算機実験も行われている。
通常の素因数分解は、有理整数環 Z で考えるが、一般の代数体の整数環においては、素因数分解の一意性に対応する性質が成り立つとは限らない。
例[編集]
360 を素因数分解する。
- 360 = 23 × 32 × 51
この右辺から分かることは、360 の正の約数は
- 2a × 3b × 5c
の形をしていて、指数は
- 0 ≤ a ≤ 3
- 0 ≤ b ≤ 2
- 0 ≤ c ≤ 1
の範囲に限られるということである。例えば
- (a, b, c) = (0, 0, 0) のとき 20 × 30 × 50 = 1
- (a, b, c) = (1, 0, 0) のとき 21 × 30 × 50 = 2
- (a, b, c) = (1, 1, 0) のとき 21 × 31 × 50 = 6
で、これらが 360 の正の約数である。
a は 0 から 3 の 4 通り、b は 0 から 2 の 3 通り、c は 0, 1 の 2 通りの場合の数をとるので、(a, b, c) の取りうる場合の数は 4 × 3 × 2 = 24(通り)である。ゆえに、360 の正の約数は全部で 24 個であると分かる。実際に 360 の正の約数は
- 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 18, 20, 24, 30, 36, 40, 45, 60, 72, 90, 120, 180, 360
の 24 個である。
素因数分解アルゴリズム[編集]
正の整数 N を素因数分解するための最も単純な方法は、2 から順に √N までの素数で割っていく方法(試し割り法)である。しかし、N が大きくなると、この方法では困難である。
大きな N に対しては以下のような方法がある。
- ρ法(ポラード・ロー素因数分解法)
- p − 1 法
- p + 1 法
- 連分数法
- 楕円曲線法 (ECM, Elliptic curve method)
- 複数多項式2次ふるい法 (MPQS, Multiple polynomial quadratic sieve)
- 数体ふるい法 (NFS, Number field sieve)
- 一般数体ふるい法 (GNFS, General number field sieve)
- 特殊数体ふるい法 (SNFS, Special number field sieve)
素因数分解の形と数[編集]
| 形 | 数 | 概要 | 整数列大辞典 |
|---|---|---|---|
| p | 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41,… | 素数 | A000040 |
| p × q | 6, 10, 14, 15, 21, 22, 26, 33, 34, 35, 38, 39,… | 相異なる素数の積 | A006881 |
| p × q × r | 30, 42, 66, 70, 78, 102, 105, 110, 114, 130,… | 楔数 | A007304 |
| p × q × r × s | 210, 330, 390, 462, 510, 546, 570, 690, 714,… | 相異なる素数の積 | A046386 |
| p × q × r × s × t | 2310, 2730, 3570, 3990, 4290, 4830, 5610,… | 相異なる素数の積 | A046387 |
| p2 | 4, 9, 25, 49, 121, 169, 289, 361, 529, 841, 961,… | 素数の平方 | A001248 |
| p2 × q | 12, 18, 20, 28, 44, 45, 50, 52, 63, 68, 75, 76,… | A054753 | |
| p2 × q × r | 60, 84, 90, 126, 132, 140, 150, 156, 198, 204,… | A085987 | |
| p2 × q × r × s | 420, 630, 660, 780, 924, 990, 1020, 1050, 1092,… | A189982 | |
| p2 × q × r × s × t | 4620, 5460, 6930, 7140, 7980, 8190, 8580,… | A189983 | |
| p2 × q2 | 36, 100, 196, 225, 441, 484, 676, 1089, 1156,… | p × q の平方 | A085986 |
| p2 × q2 × r | 180, 252, 300, 396, 450, 468, 588, 612, 684,… | A179643 | |
| p2 × q2 × r × s | 1260, 1980, 2100, 2340, 2772, 2940, 3060,… | A179690 | |
| p2 × q2 × r2 | 900, 1764, 4356, 4900, 6084, 10404, 11025,… | 楔数の平方 | A162143 |
| p2 × q2 × r2 × s | 6300, 8820, 9900, 11700, 14700, 15300,… | A189344 | |
| p2 × q2 × r2 × s2 | 44100, 108900, 152100, 213444, 260100,… | A190377 | |
| p2 × q2 × r2 × s2 × t | 485100, 573300, 749700, 762300, 837900,… | A190387 | |
| p3 | 8, 27, 125, 343, 1331, 2197, 4913, 6859, 12167,… | 素数の立方 | A030078 |
| p3 × q | 24, 40, 54, 56, 88, 104, 135, 136, 152, 184, 189,… | A065036 | |
| p3 × q × r | 120, 168, 264, 270, 280, 312, 378, 408, 440,… | A189975 | |
| p3 × q × r × s | 840, 1320, 1560, 1848, 1890, 2040, 2184, 2280,… | A179670 | |
| p3 × q × r × s × t | 9240, 10920, 14280, 15960, 17160, 19320,… | A189984 | |
| p3 × q2 | 72, 108, 200, 392, 500, 675, 968, 1125, 1323,… | アキレス数 | A143610 |
| p3 × q2 × r | 360, 504, 540, 600, 756, 792, 936, 1176, 1188,… | A163569 | |
| p3 × q2 × r × s | 2520, 3780, 3960, 4200, 4680, 5544, 5880,… | A179700 | |
| p3 × q2 × r2 | 1800, 2700, 3528, 4500, 5292, 8712, 9800,… | A179695 | |
| p3 × q2 × r2 × s | 12600, 17640, 18900, 19800, 23400, 26460,… | A190109 | |
| p3 × q2 × r2 × s × t | 138600, 163800, 194040, 207900, 214200,… | A190386 | |
| p3 × q2 × r2 × s2 | 88200, 132300, 217800, 220500, 304200,… | A190382 | |
| p3 × q3 | 216, 1000, 2744, 3375, 9261, 10648, 17576,… | p × q の立方 | A162142 |
| p3 × q3 × r | 1080, 1512, 2376, 2808, 3000, 3672, 4104,… | A179688 | |
| p3 × q3 × r × s | 7560, 11880, 14040, 16632, 18360, 19656,… | A190108 | |
| p3 × q3 × r2 | 5400, 9000, 10584, 13500, 24696, 26136,… | A190106 | |
| p3 × q3 × r2 × s | 37800, 52920, 59400, 63000, 70200, 91800,… | A190320 | |
| p3 × q3 × r3 | 27000, 74088, 287496, 343000, 474552,… | 楔数の立方 | A162144 |
| p4 | 16, 81, 625, 2401, 14641, 28561, 83521,… | 素数の4乗 | A030514 |
| p4 × q | 48, 80, 112, 162, 176, 208, 272, 304, 368, 405,… | A178739 | |
| p4 × q × r | 240, 336, 528, 560, 624, 810, 816, 880, 912,… | A179644 | |
| p4 × q × r × s | 1680, 2640, 3120, 3696, 4080, 4368, 4560,… | A179693 | |
| p4 × q2 | 144, 324, 400, 784, 1936, 2025, 2500, 2704,… | A189988 | |
| p4 × q2 × r | 720, 1008, 1200, 1584, 1620, 1872, 2268, 2352,… | A179669 | |
| p4 × q2 × r × s | 5040, 7920, 8400, 9360, 11088, 11340, 11760,… | A190107 | |
| p4 × q2 × r × s × t | 55440, 65520, 85680, 92400, 95760, 102960,… | A190384 | |
| p4 × q2 × r2 | 3600, 7056, 8100, 15876, 17424, 19600, 22500,… | A179746 | |
| p4 × q2 × r2 × s | 25200, 35280, 39600, 46800, 56700, 58800,… | A190319 | |
| p4 × q3 | 432, 648, 2000, 5000, 5488, 10125, 16875,… | アキレス数 | A179666 |
| p4 × q3 × r | 2160, 3024, 3240, 4536, 4752, 5616, 6000,… | A179698 | |
| p4 × q3 × r × s | 15120, 22680, 23760, 28080, 33264, 35640,… | A190294 | |
| p4 × q3 × r2 | 10800, 16200, 18000, 21168, 31752, 40500,… | A190115 | |
| p4 × q3 × r3 | 54000, 81000, 135000, 148176, 222264,… | A190472 | |
| p4 × q4 | 1296, 10000, 38416, 50625, 194481, 234256,… | p × q の4乗 | A189991 |
| p4 × q4 × r | 6480, 9072, 14256, 16848, 22032, 24624,… | A190012 | |
| p4 × q4 × r2 | 32400, 63504, 90000, 156816, 202500, 219024,… | A190471 | |
| p5 | 32, 243, 3125, 16807, 161051, 371293,… | 素数の5乗 | A050997 |
| p5 × q | 96, 160, 224, 352, 416, 486, 544, 608, 736, 928,… | A178740 | |
| p5 × q × r | 480, 672, 1056, 1120, 1248, 1632, 1760, 1824,… | A179667 | |
| p5 × q × r × s | 3360, 5280, 6240, 7392, 8160, 8736, 9120,… | A179704 | |
| p5 × q × r × s × t | 36960, 43680, 57120, 63840, 68640, 77280,… | A190383 | |
| p5 × q2 | 288, 800, 972, 1568, 3872, 5408, 6075, 9248,… | アキレス数 | A179646 |
| p5 × q2 × r | 1440, 2016, 2400, 3168, 3744, 4704, 4860,… | A179691 | |
| p5 × q2 × r × s | 10080, 15840, 16800, 18720, 22176, 23520,… | A190293 | |
| p5 × q3 | 864, 1944, 4000, 10976, 25000, 30375, 42592,… | アキレス数 | A179671 |
| p5 × q3 × r | 4320, 6048, 9504, 9720, 11232, 12000,… | A190011 | |
| p5 × q3 × r × s | 30240, 47520, 56160, 66528, 68040, 73440,… | A190475 | |
| p5 × q3 × r2 | 21600, 36000, 42336, 48600, 95256, 98784,… | A190470 | |
| p5 × q4 | 2592, 3888, 20000, 50000, 76832,… | A179702 | |
| p5 × q5 | 7776, 100000, 537824, 759375, 4084101,… | p × q の5乗 | A190465 |
| p6 | 64, 729, 15625, 117649, 1771561, 4826809,… | 素数の6乗 | A030516 |
| p6 × q | 192, 320, 448, 704, 832, 1088, 1216, 1458,… | A189987 | |
| p6 × q × r | 960, 1344, 2112, 2240, 2496, 3264, 3520,… | A179672 | |
| p6 × q × r × s | 6720, 10560, 12480, 14784, 16320, 17472,… | A190292 | |
| p6 × q2 | 576, 1600, 2916, 3136, 7744, 10816, 18225,… | A189990 | |
| p6 × q2 × r | 2880, 4032, 4800, 6336, 7488, 9408, 9792,… | A179703 | |
| p6 × q2 × r × s | 20160, 31680, 33600, 37440, 44352, 47040,… | A190474 | |
| p6 × q2 × r2 | 14400, 28224, 69696, 72900, 78400, 97344,… | A190469 | |
| p6 × q3 | 1728, 5832, 8000, 21952, 85184, 91125,… | A179694 | |
| p6 × q3 × r | 8640, 12096, 19008, 22464, 24000, 29160,… | A190467 | |
| p6 × q4 | 5184, 11664, 40000, 153664, 250000,… | A190464 | |
| p7 | 128, 2187, 78125, 823543, 19487171,… | 素数の7乗 | A092759 |
| p7 × q | 384, 640, 896, 1408, 1664, 2176, 2432, 2944,… | A179664 | |
| p7 × q × r | 1920, 2688, 4224, 4480, 4992, 6528, 7040,… | A179696 | |
| p7 × q × r × s | 13440, 21120, 24960, 29568, 32640, 34944,… | A190473 | |
| p7 × q2 | 1152, 3200, 6272, 8748, 15488, 21632, 36992,… | アキレス数 | A179689 |
| p7 × q2 × r | 5760, 8064, 9600, 12672, 14976, 18816,… | A190466 | |
| p8 | 256, 6561, 390625, 5764801, 214358881,… | 素数の8乗 | A179645 |
| p8 × q | 768, 1280, 1792, 2816, 3328, 4352, 4864, 5888,… | A179668 | |
| p8 × q × r | 3840, 5376, 8448, 8960, 9984, 13056,… | A179747 | |
| p8 × q2 | 2304, 6400, 12544, 26244, 30976, 43264, 73984,… | A179699 | |
| p9 | 512, 19683, 1953125, 40353607, 2357947691,… | 素数の9乗 | A179665 |
| p9 × q | 1536, 2560, 3584, 5632, 6656, 8704, 9728,… | A179692 | |
| p10 | 1024, 59049, 9765625, 282475249,… | 素数の10乗 | A030629 |
- 先頭の数はオンライン整数列大辞典の数列 A025487を参照
素元分解[編集]
整域において素因数分解(に相当する概念)を考える問題は、代数学における古典的な問題の一つである。
一般に可換環 R においては、「割り切る」という関係を単項イデアルの包含関係により定めることができる。すなわち、a, b ∈ R の生成する単項イデアル (a) = aR, (b) = bR に対し、(a) ⊃ (b) のときに a | b と書いて、a は b を割り切る、とか、a は b の約元である、とか、b は a の倍元である、などという。言い換えると、a が b を割り切るとは、b = ac を満たすような R の可逆でも 0 でもない元 c が存在することをいう。
可逆でも 0 でもない R の元が、2つの非可逆元の積として表せるとき、可約であるといい、そうでないとき既約であるという。単項イデアル (p) が自明でない素イデアルであるとき、p を素元という。素元は既約元であるが、一般に逆は成立しない。
素元分解整域[編集]
環 R の元を既約元の積に表すことを既約元分解、素元の積に表すことを素元分解という。既約元分解が一意であるような環を素元分解整域もしくは一意分解環という(任意の元が素元の積に表せるなら、その表し方は一意である)。有理整数全体の成す環 Z や体上の多項式環 K[x] などは素元分解整域である(高校数学でいう多項式の“因数分解”とは、通常有理数体 Q 上の一変数多項式環における素元分解のことである)。これらの環はユークリッド整域にもなっているが、一般にユークリッド整域は単項イデアル整域であり、単項イデアル整域は素元分解整域になる。
素元分解整域でない例として有理数体 Q に方程式 x2 + 5 = 0 の根を添加した代数体 Q(√−5) の整数環 Z[√−5] で 6 を既約分解することを考えてみる。整数 Z の範囲では 2 × 3(と同値なもの)のみであるが、Z[√−5] の範囲では
- 6 = 2 × 3 = (1 + √−5)(1 − √−5)
と本質的に異なる2通りに既約分解される。したがって Z[√−5] は素元分解整域ではない。しかし、イデアルとしては (2), (3) や (1 ± √−5) はさらに分解できて、素イデアルの積としては一意に
- (6) = (2, 1 + √−5)2(3, 1 + √−5)(3, 1 − √−5)
と分解される。一般に、代数体の整数環はデデキント環であり、素イデアルの積に一意的に分解する。
このような考察はクンマーの理想数の理論に始まると考えられる。クンマー以降、デデキントのイデアル論などを経て代数的整数論の基盤となっている。
素因数分解の記録[編集]
Cunningham Project とは、b = 2, 3, 5, 6, 7, 10, 11, 12 および多くの自然数 n に対し、bn ± 1 を素因数分解しよう、というプロジェクトである。RSA チャレンジについてはRSA暗号#RSA暗号解読コンテスト を参照。
- 2005年4月:11281 + 1 の約数として現れる176桁の合成数が素因数分解される(一般数体ふるい法、立教大学、NTT、富士通研究所)
- 2005年5月:200桁の合成数 RSA-200(RSAチャレンジ)が素因数分解される(一般数体ふるい法、Bahr, Boehm, Franke, Kleinjung)[1]
- 2006年8月:10381 + 1 から67桁の素数が分解される(楕円曲線法、B. Dodson)
- 2006年9月:7352 + 1 の約数として現れる128桁の合成数が素因数分解される(一般数体ふるい法、情報通信研究機構、富士通、富士通研究所、フィールドプログラマブルゲートアレイおよびダイナミックリコンフィギュラブルプロセッサを用いた専用ハードウェアを初めて使用)
- 2007年5月:21039 − 1 の約数として現れる307桁の合成数が素因数分解される(特殊数体ふるい法、NTT、ドイツのボン大学、スイス連邦工科大学との共同研究)
- 20??年: 200桁(663ビット)
- 2010年1月:232桁(768ビット)(NTT、スイス連邦工科大学ローザンヌ校 (EPFL)、独ボン大学、フランス国立情報学自動制御研究所 (INRIA)、オランダ国立情報工学・数学研究所 (CWI)。一般数体ふるい法。300台PCの並列計算処理。約3年)
関連項目[編集]
脚注[編集]
注[編集]
出展[編集]
参考[編集]
- 和田秀男、『コンピュータ素因子分解』、遊星社、1987、改訂版 1999、ISBN 978-4795268890
- 和田秀男、『素数全書-計算からのアプローチ』(訳書、R.Crandall、C.Pomerance著)、朝倉書店、2010、ISBN 978-4254111286
- 山本, 芳彦 『数論入門』 岩波書店〈現代数学への入門〉、2003年。ISBN 4-00-006878-4。