スムーズ素数

定義

素数$p$が多くの約数を持っている場合、$(p-1)$であれば$p$をスムースな素数と言う。
$B$以下の素数の積で表される数を**$B$-スムース数**と言う。
$\psi ( X , B )$は、$X$以下の$B$-スムース数の個数を表す。

説明

スムースな素数の例として$p=37$を考えると、$(p-1)$は$p-1 = 36 = 2^2 3^2$のような細かい素数の積で表される。スムースという概念は、暗号学が発展するにつれて、暗号化に適さない素数を表すために導入されたものと考えても良い。

$5$-スムース数の例として $$ 2,3,4,5,6,8,9,10,12,15,16,18 \cdots $$ があり、$5$-スムース数ではない例として $$ 7,11,13, 14, 17,19,21,22,23,26,28,29,31,33\cdots $$ がある。

$\psi : \mathbb{N}^2 \to \mathbb{N}_{0}$は典型的なカウント関数で、例えば$\psi (25,5)$を考えると、$25$以下の$5$-スムース数は$2,3,4,5,6,8,9,10,12, $$ 15,16,18 ,20,24,25$で$15$個ある。したがって、$\psi (25,5) = 15$のように表すことができる。