エラトステネスの篩

エラトステネスの篩（ふるい）とは、素数を求めるアルゴリズムである。

概要

自然数を並べ、初めに1をマークし、次に2をマークして2の倍数を消去する。

次に残った数で一番小さい3をマークし3の倍数を消去する。

次に残った数で一番小さい5をマークし…

といった作業を繰り返すことで、素数を求めることができる。以下は100までの表。赤色が素数である。

1	2	3	4	5	6	7	8	9	10
11	12	13	14	15	16	17	18	19	20
21	22	23	24	25	26	27	28	29	30
31	32	33	34	35	36	37	38	39	40
41	42	43	44	45	46	47	48	49	50
51	52	53	54	55	56	57	58	59	60
61	62	63	64	65	66	67	68	69	70
71	72	73	74	75	76	77	78	79	80
81	82	83	84	85	86	87	88	89	90
91	92	93	94	95	96	97	98	99	100

エラトステネスの篩のいいところはnまで作業が終わればn²までの素数が漏れなく求まるというところである。この表で言えば10以下の素数を見つける手順が終わった時点で100までの素数すべてが明らかになる。

欠点はマークした素数以上の全ての数を毎回チェックして回る必要があるため時間がかかるところ。工夫しないとN以下の素数を調べるのにO(N√N)くらいの時間がかかるらしい。

また、途中で表を大きくしようとしたい場合、追加した分を初めから埋め直す必要がある。さらに、大きな素数を求める場合でも2から始めないと数え漏れが出てしまうので融通が利かないというところも欠点。

多項式環に対するエラトステネスの篩

既約多項式とは、それ以上小さな次数の多項式に因数分解できない多項式を指す。同じ多項式でも係数体により既約か可約か変化する。

整数を素数pで割ったあまりで分類すると有限体F_pになる。F_pの元を係数とする多項式f(x)∈F_p[x]を考える。例えば、F₂係数多項式f(x)∈F₂[x]は係数が0または1の多項式である（1+1=0に注意して計算する）。f(x)が既約であるかどうかをエラトステネスの篩を用いて列挙する事で判別できる。

準備として、多項式をその係数のみで表すことにする。例えば、F₂[x]においてx³+x²+1 → 1101、(x+1)(x²+x)=x³+x → 11×110=1010。F₃[x]において(x+2)(2x+1)=2x²+2x+2 → 12×21=222。単純な2進数や3進数とは異なることに注意。

• F₂[x]におけるアルゴリズム

1. 多項式を小さい順から列挙し、1にマークする。次にxにマークし、xにx以上の多項式を掛け算して列挙したものを消去する。
2. 次に、残った多項式で一番小さな多項式x+1をマークし、残った多項式を小さな順から掛け算して列挙したものを消去する。
3. 以下繰り返し、マークされた多項式が既約多項式、消去された多項式が可約多項式である。

1	10	11	100	101	110	111	1000
1001	1010	1011	1100	1101	1110	1111	10000
10001	10010	10011	10100	10101	10110	10111	11000
11001	11010	11011	11100	11101	11110	11111	100000

この表からF₂[x]において、x,x+1,x²+x+1,x³+x+1,x³+x²+1、x⁴+x+1,x⁴+x³+1、x⁴+x³+x²+x+1、…が既約多項式と分かった。

• F₃[x]におけるアルゴリズム

1. 初めに1,2をマークする。xにマークし、xとx以上の多項式を掛け算して列挙したものを消去。
2. 残った多項式で最小のx+1にマークし、x+1とx+1以上の残った多項式を掛け算して列挙したものを消去。
3. 以下繰り返し、残った物のうち係数が全て2の物を消去する。最後に残った多項式が既約多項式。

1	2	10	11	12	20	21	22	100
101	102	110	111	112	120	121	122	200
201	202	210	211	212	220	221	222	1000
1001	1002	1010	1011	1012	1020	1021	1022	1100
1101	1102	1110	1111	1112	1120	1121	1122	1200
1201	1202	1210	1211	1212	1220	1221	1222	2000
2001	2002	2010	2011	2012	2020	2021	2022	2100
2101	2102	2110	2111	2112	2120	2121	2122	2200
2201	2202	2210	2211	2212	2220	2221	2222	10000

この表から、F₃[x]においてx,x+1,x+2,2x+1,x²+1,x²+x+2,x²+2x+2,…が既約多項式と分かった。

論理的背景

これは環論における一意分解整域の素イデアルを生成元の小さなイデアルから列挙するアルゴリズムである。

既約多項式は多項式環において素数のような役割を持つが、一般に多項式の既約判定は難しい。しかし、既約判定の一つとして有限体係数に限定して判定する方法があり、F_p[x]で既約→Z[x]で既約→Q[x]で既約、が一般に成り立つ。有理係数を定数倍して整数にし、適当な素数で合同をとることでQ[x]をF_p[x]で判断する事が可能な場合がある。係数をF_p[x]に限定するのは、Z[x]だと1次式の時点で無限個あり作業が終わらないためである。

F₂[x]でx²+x+1が既約と分かったが、係数を2で割ったあまりが同じになる多項式、x²+3x+1, x²+x+3, x²+3x+3、…あるいはF₃[x]でx²+2x+2は既約だったが、係数を3で割ってと同じになるx²+2x+5, x²+5x+2、…などもZ[x]、ひいてはQ[x]において既約多項式である。F₂[x]においてx³+x²+1が既約であると知っていれば、3x³+27x²+14x+7が既約多項式であるとすぐに判別できるのである。

F₃[x]のアルゴリズムは多項式環F₃[x]の素イデアル(f(x))を列挙する作業に相当する。最後に途中まで素イデアルと同じ振る舞いをする、素数から生成されたイデアル(2,f(x))を排除し既約多項式の定数倍を除いている。

自然数の場合と同じように、n番目までの既約多項式を求めればn²番目までの既約多項式が漏れなく列挙できる。具体的にはn次多項式で判定が終われば2n次多項式までの既約多項式が得られる。

欠点も大体同じで、時間がかかること、次数のおおきな多項式が既約かどうか調べたい時でも1次の多項式から調べないと列挙漏れが出てしまうこと、表の拡張がしにくいことが挙げられる。また、あらゆる素数pでF_p上可約だがZ上既約という多項式も存在するので万能ではないという事もある。

関連動画

関連項目

• 算数、数学
• アルゴリズム
• 数学関連用語の一覧
• 自然数
• 素数
• 多項式
• 環(数学)
• 体(数学)