数値演算法 (6) 素数判定法

RSA暗号の紹介の中で、公開鍵として二つの素数が必要となることを説明しました。サンプル・プログラムの中では非常に小さな数を使って公開鍵を作成したため、素数であるか判別するためには実際に素因数分解できるか試していたのに対し、実際の処理においては数百桁もの数値を扱うため、素因数分解を使って素数であるかを判断することは不可能になります(そもそも RSA暗号は、素因数分解が困難であることを前提にした暗号です)。実は、素数であるかどうかを判定することは、素因数分解を行わなくても可能です。素数でないことが分かったとしても、それを素因数に分解することはできないというのも不思議な気がしますが、例えば以前紹介した「フェルマーの小定理」を使えば、合成数であることは素因数分解をしなくても判断可能です。 この章では、素数であるかどうかを判定する方法について紹介したいと思います。 ● 総和(Σ)と総積(Π)の記法