素数Ⅱ

間違っている気がする素数の考え方
HTMLを無理矢理コピー。
素数統計のとり方
素数の定義
素数とは、
1とその数以外で割れない数のこと。
但し、1は含めないものとする。
つまり、定義を式で表すと、
xを素数とした時、
yを自然数(y≠x,y≠1)として、
0 ≡ x (mod y)ではない
ということである。
素数の基本的なこと
2と5
2:偶数で唯一素数である。

　(但し、特殊扱いするのは間違いかもしれない)
5:下1ケタが5の数の中で唯一素数。

　(略)
それ以外の素数
　　3,7,11,13,17,19...
　　これらに共通するのは、
　　下一桁1,3,7,9であること
　　である。
　　しかし、これでは何か分からないので、
　　どういうことかを説明すると、
　　1:素数の可能性あり
　　2,4,6,8:偶数。(なし)
　　3:素数の可能性あり
　　5:5の倍数。
　　7,9:素数の可能性あり
　　ということで、候補を絞ることができる。
素数で全て表される
合成数
　　全ての自然数は素数か合成数であるから、
　　全て素数×素数(×素数...)になる。
偶数
　　現在未証明であるが、
　　全ての偶数は素数の和で表される
　　という予想がある。(それだけ)
素数の統計
くだらない前座は棚に上げて、本題に移ろう。
素数の見つけ方
現在使われているものは、
メルセンヌ素数から発見する、
という手法。(2のn乗-1となる素数を探す)
素数の条件(数字的見た目)
　一.先程紹介した下1桁1,3,7.9　(合成数多し) 　ニ.「どの倍数でもない」こと　 (例外無し) 　　　の二つ。　
素数とは?
　定義より、数の頭である。
　どういうことかというと、
2,4,6,8..
3,6,9..
5,10..
7,14..
11,22..
13,26..　と並べた時、
　先頭に来る数は素数だから、である。
このように表を作って探すこともできた。
(筆者は2~997まで試したが、2日かかった)
このようにしらみつぶしにするのは
時間がかかるので、大きい桁には効果なし。
そこで、
ランダムに数を作り、判定する方法が取られ、
COMを使った計算や素数定理を駆使して
研究が進められている。
　注:素数定理は桁が多くなるにつれて、
　　素数の数をLixで近似できるというもの。
桁が上がるにつれて精度が上がる。ありがたい。
計算量
下1桁1,3,7,9で全て計算の2/5
全ての数で割るのではなく、
　　x/10よりも小さい素数で割ることで
　　計算量は1/10以下(但し後で3,7で割る必要あり)
　素数をいちいち計算して
　　それで割るのではなく、
　　素数をメモリに記録しておくことで
　　計算量は1/(x以下の素数計算量)
また、双子素数は少ないので
　等間隔に乱数を発生させる
　　アルゴリズムを作り、
(例：素数でない→次の数
　　　素数だ→対象/素数定理
　　　　　で予想した数だけジャンプする
乱数としては偏りが生じないように
未解明の無理数(円周率、√2等)の桁を使用
既存の素数×?+余りの数
既存の素数2つを、
見た目上の合体(10π①+π②)
　　(但しπ①,②は巨大素数、π①≠π②)
→割り切れない可能性有(少なくともx/11はOK)
素数の使い道
RSA暗号の計算(RSA2048bitとか)
新認証システム開発
例：チャレンジ乱数Cの送信→
　　　足すとC/Aの余りがX増加する数を計算し、
　　　　それを足し、Yと定義する→
　　　送られた数Yの余りを計算し、
　　　　合っていれば認証。
但し、CによってA,Xが変化するものとし、
サーバー側にはC,Yの対応表があるものとする。 →
c (Mod a) + x ≡ y (Mod a)
但しa,xはcの関数である
解説:Cをaで割った余り+X=Yをaで割った余り
この時、素数をcに用いることで、
0 ≡ c (mod a) でないを実現する。
　　注:0 ≡ c (mod a)の時、
　　　a≡y mod aとなるため
　　　cに対応するaが一つずつバレる