素数と暗号化

暗号化で素数を使ったりするという話があった。

httpsで使われる暗号化方式なんだけれど、
これはコンピュータが素数を見つけるのに時間がかかるという話から。

まあ、そんな話は今の処理速度とキーの長さとの兼ね合いで
イタチごっこだったりするらしい。

素数かどうかを見つけるルーチンを考えるのだけれど

単純にループさせて割って余りが出たら素数ではないので処理終了、
ってやつ。

nが素数かどうかをチェックするのに

for i=2 to n-1

で n/i に余りが無かった時点で処理終了、ってやつ。

でも、最初に　i=2
ってことは、終了が
n-1
ではなく
n/2
で良いはず。

と、ここで気づく。

iが3まで判定したら

n/3まで

つまり
for i=2 to n/i
でしょ。

これで早めに判定できそうだ。

これって
iの間チェックするし、i>0だから
i^2i^2-n<0
(i-(sqrt(n))(i+(sqrt(n))<0
sqrt(n)>0,i>0
だから
(i-(sqrt(n))<0
i
ってことで、最初から
for i=2 to sqrt(0)
で良いんだね。

そりゃそうか。
自身が素数の平方ならソレが最大だからね。