素数p は、1 よりも大きな自然数で、 1 とそれ自身でしか因数分解ができない数である。2, 3, 7, ... とあるが、素数を予測する数列などが発見されておらず (2012 年現在)、 素数の発見のためには総当たりで調べることしかできない。
RSA 暗号は、素数で作られた冪の余りを使って公開鍵を作り、 それを使って暗号化した電子文書を公開鍵の所持者が解読する。
Ruby 1.9 で素数を扱うライブラリについては こちらで。