스무스 소수

스무스 소수

Smooth prime

정의

  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$ 와 같이 나타낼 수 있다.

댓글