『素数探求』
数学二班
邵
博文，黒田
峻，松本能和
■研究動機
・小学校のときに学んだ素数について、一見すると不規則な素数の分布も何か規則性があ
るのではないかと気になって興味深く調べていた。また、素数が私たちの実生活に、どの
ように利用されているか知りたいと思い、この機会にさらに詳しく研究することにした。
■研究内容
（1） エラトステネスのふるい
素数を効率よく見つける方法の１つ。数を並べ，小さい素数から順にその倍数を消
していく。n までの素数を探したいときは，√n 以下の数の倍数を消せばよい。
（2） 素数砂漠
素数が連続して見つからない数の並び。いくらでも長い素数砂漠を見つけることが
できる。
＜証明＞ある自然数を N とする。
N！は 2～N までの自然数で割り切れるので合成数である。2 は 2 の倍数なので N！
＋2 は 2 の倍数である。同様に N！＋3，N！＋4，N！＋5 もそれぞれ 3,4,5 で割り
切れる。このように考えていくと，
N！＋2，N！＋3，N！＋4,・・・・・・,N！＋（N－1），N！＋N
はすべて合成数である。これは長さ N－1 の素数砂漠である。このことは任意の自
然数全てについて成り立つ。よって，いくらでも長い素数砂漠を見つけられる。
（3） 素数の無限性の証明
素数が有限の n 個しかないと仮定し，それらを p1，p2，p3・・・・pn とする。
N=１＋p1×p2×p3×・・・・・・×pn
とおくと，N は存在するすべての素数 p1，p2，p3・・・pn で割っても 1 余るので割
り切れないことになる。よって，N は pn より大きい素数である。これは素数が有限
個しかないという最初の仮定に矛盾する。したがって，素数は無限個である。
（4） 双子素数
差が 2 である 2 つの素数の組。2 と 3 の組を除くと，双子素数は最も数の近い素数
の組である。無限にあると考えられているが証明はされていない。 三つ子素数
差が 2 である 3 つの素数の組。3, 5, 7 の組しかない。
＜証明＞3 つの素数を n、n＋2、n＋4 とする。背理法で証明する。
[1]n が 3 の倍数のときはｎが素数なので考えなくてよい。
[2]n が 3 の倍数+1 と仮定すると
n=3k+1 とおける。
-35-
このときは n+2 が 3 で割り切れるので、素数であることに矛盾。
[3]n が 3 の倍数+2 と仮定すると n=3k+2 とおける。
このときは、n+4 が 3 で割り切れるので、素数であることに矛盾。
(5)
完全数
完全数はその数自身を除く約数の和がそれと同じになる数。
完全数は今のところ偶数だけであり、奇数の完全数が存在するかどうかは未確認。
偶数の完全数は 2N－1 が素数であるような正の整数 N を用いてｎ=2N－1(2N－1)とい
う形であらわせる。（6）で出てくる「メルセンヌ素数」が一つ見つかれば、それに
対応した完全数が見つかる。例 6=1+2+3 28=1+2+4+7+14
(6) メルセンヌ数
n を自然数とする。2ｎ－1 の式で表せることのできる数をメルセンヌ数という。
特にこの数が素数のとき｢メルセンヌ素数｣という。
「2ｎ－1 がメルセンヌ素数ならば 2ｎ-1(2ｎ－1)は完全数である」
＜証明＞
2n－1 が素数のとき 2n－1(2n－1)の自分自身を含む約数の総和は
（1+2+・・・+2n－1）{1+(2n－1)}
である。一つ目のカッコは等比数列の和の公式から 2n－1 である。
（2n－1）・2n となり元の数 2n－1(2n－1)の２倍となる。
よって 2n－1(2n－1)は完全数である。
(7) 合同式
a と b の n で割ったあまりが等しいことを、a≡ｂ（mod n）と書く。次のような性
質があることが容易に確かめられる。
(8) フェルマーの小定理
p は素数で、a と p が互いに素であるとき
ap-1 ≡ 1 (mod p)
-36-
（証明）まず、数学的帰納法を用いて次の式を証明する
ap ≡ a (mod p)
Ⅰ）a=1 のとき
ap=1 (mod p)である。
明らかに
Ⅱ）a = m のとき成り立つと仮定すると
mp ≡ m (mod p)
a = m+1 のとき
a p =(m + 1)p= mp + pC1mp−1 + pC2mp−2 + … + pCp−1m + 1（二項定理）
ここで、二項係数 pCk について pCk =
ｐ！
ｋ！(ｐ−ｋ)！
p は素数で、k < p より、分子に含まれる p は約分されることはないから二項
係数 pCk は全て p の倍数である。ゆえに、
(m + 1)p ≡mp + 1(mod
(m + 1)p ≡m+1(mod
p
よって、a
≡
p) ここで、仮定より mp ≡m(mod p)なので
p)
a (mod p) が証明された。
a と p は互いに素なので、合同式の性質より両辺を a で割って
ap-1 ≡ 1 (mod p)を得る。
(9)
ＲＳＡ暗号
ＲＳＡ暗号は、1977 年 MIT（マサチューセッツ工科大学）に勤務していた Rivest
（リベスト）
、Shamir（シャミア，シャミール）、Adleman（エイドルマン，アド
ルマン） という三人の研究者により作られた暗号である。 この暗号は三人の名
前の頭文字をとって ＲＳＡ暗号（アール・エス・エー暗号）と名付けられた。
《ＲＳＡ暗号の仕組みと安全性》
ＲＳＡ暗号は、自由に選んだ異なる 二つの素数を掛けた数 を法とする世界を利
用する。その仕組みの根本は次の定理である。この定理は前述の“フェルマーの
小定理”から導かれる。
p，q は異なる素数で、a が p q の倍数でないとき
a(p-1)(q-1)+1 ≡ a (mod pq)
この定理は、２つの素数（ P, Q とする）をかけた数を法とする世界では、全ての数
が元に戻るべき乗数が存在することを示している。全ての数は、( P－1 ) × ( Q－1 ) +
1 回だけ、べき乗した時に必ず元の数に戻る。 例として、二つの素数に 3 と 11 を
選び、これらを掛けた数 33 を法とする世界を考えてみる。 代入して計算すると、
33 を法とする世界では、どんな数も 21 乗すると自分自身に戻せるとわかる。図のよ
-37-
うに元の数を 2 乗、3 乗、としていくたびに、予想のつかない数になっているが、21
乗した時だけ、自分自身に戻っている。
例として、元の数を 7 乗してみる。この数は、元の数を 7 乗して、33 で割った余り
なので、簡単には自分自身に戻すことはできない。しかし、この数は、さらに 3 乗
するだけで、簡単に自分自身に戻すことができる。この暗号の安全性を説明するた
め、もう少し大きな数で考えてみる。6887 を法とする世界でも、何乗かすれば自分
自身に戻るのだがそれは何乗だろうか。実は 6721 乗するとすべての数字が自分自身
に戻ることがわかるのだが、それは 6887 を 71 と 97 に素因数分解できて初めてわか
るのだ。素因数分解は、人間の勘と長年の経験 によるところが非常に大きく、巨大
な二つの素数を掛け合わせた数を短時間で素因数分解する効率的な方法は見つかっ
ていないのである。４桁の数字でさえ簡単に素因数分解できないのだから実際に
RSA 暗号で使われている３００～６００桁もの素数を素因数分解するのはほぼ不可
能である。ちなみに 16 年前は１２９桁の数を素因数分解をするのに１０００台もの
コンピューターをつなげて、半年間計算させなければならなかった。この素因数分
解の困難性が、ＲＳＡ暗号の安全性を保証している。
べき乗
元の数
２
乗
３
乗
４
乗
５
乗
６
乗
７
乗
８
乗
９
乗
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
1
4
9
16
25
3
16
31
15
1
22
12
4
31
27
25
25
27
31
4
12
1
8
27
31
26
18
13
17
3
10
11
12
19
5
9
4
29
24
28
14
21
1
16
15
25
31
9
25
4
27
1
22
12
16
4
3
31
31
3
4
16
12
1
32
12
1
23
21
10
32
12
10
11
12
10
23
12
1
32
21
10
23
21
1
31
3
4
16
27
4
25
9
1
22
12
31
25
15
16
16
15
25
31
12
1
29
9
16
14
30
28
2
15
10
11
12
7
20
27
25
8
6
13
26
21
1
25
27
31
4
15
31
16
3
1
22
12
25
16
9
4
4
9
16
25
12
1
17
15
25
20
24
19
29
27
10
11
12
28
26
3
31
2
30
7
5
21
・
・
・
・
・
・
・
・
・
・
・
・
・
・
・
・
・
・
・
・
・
・
・
・
・
・
・
・・・ ・・・ ・・・ ・・・ ・・・ ・・・ ・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・
・
・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・
・
・
・
・
・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・
・
・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・
・
・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・
・
・
・
・
・
１
７
乗
１
８
乗
１
９
乗
２
０
乗
２
１
乗
２
２
乗
２
３
乗
1
29
9
16
14
30
28
2
15
10
11
12
7
20
27
25
8
6
13
26
21
1
25
27
31
4
15
31
16
3
1
22
12
25
16
9
4
4
9
16
25
12
1
17
15
25
20
24
19
29
27
10
11
12
28
26
3
31
2
30
7
5
21
1
1
12
1
1
12
1
1
12
1
22
12
1
1
12
1
1
12
1
1
12
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
1
4
9
16
25
3
16
31
15
1
22
12
4
31
27
25
25
27
31
4
12
1
8
27
31
26
18
13
17
3
10
11
12
19
5
9
4
29
24
28
14
21
・
・
・
・
・
・
・
・
・
・
・
・
・
・
・
・
・
・
・
・
・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
・・・
■今後の展望・疑問
素数の判定方法の研究や素数を生み出す素数生成式を作れないか。実生活に役立って
いる場面は他にどのようなものがあるか。など研究を深めてみたいと思っている。
■参考文献
http://mathtrain.jp「高校数学の美しい物語」
https://www.maitou.gr.jp/rsa/「サルにも分かる RSA 暗号」
図解雑学 暗号理論 (ナツメ社)
面白くて眠れなくなる数学（ＰＨＰ研究所）
-38-
© Copyright 2024 ExpyDoc
