エラトステネスの篩

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

概要

自然数を並べ、初めに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)くらいの時間がかかるらしい。また途中で表を大きくしようとしたい場合、追加した分を初めから埋め直す必要がある。

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

既約多項式とは、それ以上小さな次数の多項式に因数分解できない多項式を指す。

整数を素数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+1,x²+x+2,…が既約多項式と分かった。

有理数係数多項式の既約判定は難しいが、F_p[x]で既約→Z[x]で既約→Q[x]で既約、が一般に成り立つ。逆方向は必ずしも成り立たない。

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]において既約多項式である。F₂[x]においてx³+x²+1が既約であると知っていれば、3x³+25x²+14x+7が既約多項式であるとすぐに判別できるのである。

このアルゴリズムは多項式環F_p[x]の素イデアル(f(x))を列挙する作業に相当する。最後に途中まで素イデアルと同じ振る舞いをする極大イデアル(a,f(x))を排除している。

関連動画

関連項目

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