素因数分解

出典: フリー百科事典『ウィキペディア(Wikipedia)』
ナビゲーションに移動 検索に移動

素因数分解 (そいんすうぶんかい、: prime factorization) とは、ある正の整数素数の形で表すことである。ただし、1 に対する素因数分解は 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 までの素数で割っていく方法である(Trial division英語版)。しかし、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

素元分解[編集]

整域において素因数分解(に相当する概念)を考える問題は、代数学における古典的な問題の一つである。

一般に可換環 R においては、「割り切る」という関係を単項イデアルの包含関係により定めることができる。すなわち、a, bR の生成する単項イデアル (a) = aR, (b) = bR に対し、(a) ⊃ (b) のときに a | b と書いて、ab を割り切る、とか、ab の約元である、とか、ba の倍元である、などという。言い換えると、ab を割り切るとは、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暗号解読コンテスト を参照。

関連項目[編集]

注釈[編集]

  1. ^ 空積を 1 とする規約のもと、1 を特別扱いする必要はない(すなわち 1 は 0 個の素数の積である)。また、素数 p の素因数分解は p であり(すなわち p は 1 個の p の積である)、"素数は素因数分解できない"という表現は誤りである。

参考[編集]

外部リンク[編集]