📂整数論

スムーズ素数

定義

1. 素数$p$が多くの約数を持っている場合、$(p-1)$であれば$p$をスムースな素数と言う。
2. $B$以下の素数の積で表される数を**$B$-スムース数**と言う。
3. $\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$のように表すことができる。