평활수

숫자 이론에서 n-smooth(또는 n-friable) 숫자는 주요 요인이 모두 n보다 작거나 같은 정수다.^[1][2] 예를 들어, 7-smooth 숫자는 모든 주요 요인이 최대 7인 숫자여서 49 = 7과² 15750 = 2 × 3² × 5³ × 7 모두 7-smooth인 반면 11과 702 = 2 × 3³ × 13은 7-smooth가 아니다. 이 용어는 레오나드 애들레만에 의해 만들어진 것 같다.^[3] 정수의 인자화에 의존하는 암호학에서는 매끄러운 숫자가 특히 중요하다. 2-smooth 숫자는 2의 힘에 불과하며 5-smooth 숫자는 정규 숫자로 알려져 있다.

정의

양정자를 부른다. B-주요인 중 다음보다 큰 요소가 없는 경우 B예를 들어, 1,620은 프라임 인자화 2² × 3⁴ × 5를 가지고 있다. 따라서 1,620은 그것의 프라임 인자가 5보다 크지 않기 때문에 5-매끄러움이다. 이 정의에는 일부 작은 주요 요인이 결여된 숫자가 포함된다. 예를 들어, 10과 12는 각각 주요 요인 3과 5를 놓치더라도 5-smooth이다. 모든 5-smooth 숫자는 2^a × 3^b × 5^c 형식이며, 여기서 a, b, c는 음이 아닌 정수다.

5-smooth 숫자를 정규 숫자 또는 해밍 숫자라고도 하며,^[4] 7-smooth 숫자를 미천한 숫자라고도 하며,^[5] 때로는 고도로 합성된 숫자의 다른 의미와 충돌하기도 한다.^[6]

여기, 참고하십시오. B 그 자체는 a의 요소들 사이에 나타날 필요가 없다. B-csv 번호. 숫자의 가장 큰 주요 요인이 다음과 같은 경우 p 그러면 그 숫자는 B-누구에게나 좋은 것 B ≥ p. 많은 시나리오에서 B 소수지만, 복합적인 숫자도 허용된다. 숫자는 B-인 경우 및 인 경우만 p-message, where p 다음보다 작거나 같은 최대 프라임 B.

적용들

매끄러운 숫자의 중요한 실용적인 적용은 빠른 FFT(Fast Fourier Transform) 알고리즘이다(Cooley- 등).Tukey FFT 알고리즘)은 주어진 크기 n의 문제를 요인 크기의 문제로 재귀적으로 분해하여 작동한다. B-smooth 숫자를 사용하면 효율적인 알고리즘이 존재하는 이 반복의 기본 사례가 작은 소수임을 보장할 수 있다. (큰 프라임 크기는 블루스타인의 FFT 알고리즘과 같은 덜 효율적인 알고리즘을 필요로 한다.)

바빌로니아 수학에서 5-smooth 또는 정규 숫자는 특별한 역할을 한다.^[7] 그것들은 음악 이론에서도 중요하며(Limit (음악)^[8] 참조), 이러한 숫자를 효율적으로 생성하는 문제는 기능 프로그래밍의 시험 문제로 이용되어 왔다.^[9]

매끄러운 숫자는 암호 해독에 많은 응용이 있다.^[10] 대부분의 애플리케이션이 암호 분석(예: 가장 빠르게 알려진 정수 인자화 알고리즘: 일반 번호 필드 체 알고리즘)을 중심으로 하는 반면 VSH 해시 함수는 신뢰할 수 있는 안전한 설계를 얻기 위해 부드러움을 건설적으로 사용하는 또 다른 예다.

분배

$\psi {\displaystyle \mathrm{}}$(${\displaystyle x}$, y${\displaystyle }$) ${\displaystyle \Psi (x,y)}$은(는) x보다 작거나 같은 y-smooth 정수의 수를 나타낸다$$(de Bruijn 함수).

부드러움 바인딩 B가 고정되고 작으면 ${\displaystyle :}$ (${\displaystyle x}$, ${\displaystyle B}$) ${\displaystyle \Psi (x,B$

${\displaystyle \PSI(x,B)\심(\frac {1}{\pi(B)!}}}\prod _{p\leq B}{\frac {\log x}{\log p}}.}$

여기서 $\pi {\displaystyle }$(${\displaystyle B}$) ${\displaystyle \pi (B)}$은(는$)$ B {\$displaystyle$ B}보다 작거나 같은 프리타임 수를 나타낸다$.$

그렇지 않으면 매개 변수 u = log x / log y: 즉, x = y로^u 정의하십시오. 그러면

${\displaystyle \Psi(x,y)=x\cdot \rho(u)+O\왼쪽({\frac {x}{\log y}}\오른쪽)}$

여기서 $\rho {\displaystyle (u}$ )${\displaystyle \rho(u)}$은(는) Dickman 함수다.

주어진 크기의 수에서 부드러운 부분의 평균 크기는 $\zeta {\displaystyle }$(${\displaystyle u}$) ${\displaystyle \zeta (u$로 알려져 있으며, and${\displaystyle }$(${\displaystyle u)}$ ${\displaystyle \rho (u)}$보다 훨씬 더 느리게 부패하는 것으로 알려져 있다$.$^[11]

어떤 k에 대해서도 거의 모든 자연수는 k-smooth가 아닐 것이다.

파워스무스 수

또한, 모든 주요 강국 p ${\$분할 m이 충족되면 m을 B-powersmooth(또는 B-ultrafriable)라고 부른다.

${\displaystyle p^{\nu}\leq B.\,}$

예를 들어, 720 (2⁴ × 3² × 5¹)은 5-매끄러우나 5-파워매틱은 아니다(예: ${\displaystyle {3\mathrm{}}^{}}$ $2{\displaystyle {\mathrm{}}^{}}$= ${\displaystyle 9}$ ${\displaystyle \nleqq }$ ${\displaystyle 5}$ ${\displaystyle$ 3$^{2}=9\nleq$ 5$},$ ${\displaystyle 2^{}}$ = 16${\displaystyle 16}$ 5 ${\displaystyle 2^}=16\nleq 5}).$ 최대 프라임인자 파워가⁴ 2=16이기 때문에 16파워가 부드럽다. 그 숫자도 17파워스무스, 18파워스무스 등이 있다.

B-smooth와 B-powersmooth 숫자는 폴라드의 p - 1 알고리즘과 ECM과 같이 숫자 이론에 응용된다. 이러한 애플리케이션은 종종 B가 지정되지 않은 "원활한 숫자"로 작동한다고 한다. 이는 관련 숫자가 일부 불특정 소수 숫자 B에 대해 B-힘이 부드러워야 함을 의미한다. B가 증가하면 해당 알고리즘이나 방법의 성능이 급격히 저하된다. 예를 들어, Pohlig-이산 로그 계산을 위한 Hellman 알고리즘은 B-smooth 순서 그룹에 대해 O(B^1/2)의 실행 시간을 가진다.

A 세트에 걸쳐 매끄러움

더욱이, m은 A에서 인자가 원소의 힘인 m의 인자가 존재하는 경우 정해진 A에 걸쳐 매끄러워진다고 한다. 예를 들어 12 = 4 × 3, 12는 A₁ = {4, 3}, A₂ = {2, 3} 및 $Z{\displaystyle \mathbb{}}$ ${\$ {Z$}}$ 집합에 대해 부드럽지만, 12 = {3, 5}에는 A에 없는₃₃ 요인 4 = 2가² 포함되어 있기 때문에 A = {3, 5} 집합에 대해서는 부드럽지 않다$.$

집합 A는 주요 요인의 집합일 필요는 없지만, 일반적으로 딕슨의 인자화 방법 및 2차 체의 인자 베이스에서 볼 수 있는 적절한 소수 부분 집합이다. 마찬가지로, 그것은 동형상 $ism{\displaystyle }$:${\displaystyle Z}$ [ ]${\displaystyle ]}$ →${\displaystyle Z\mathbb{}}$ / ${\displaystyle n\mathbb{}}$ ${\displaystyle Z}$ ${\$:\$mathb${Z$}[\theta$][\theta ]][\to $\mathb${Z$} /$n$\mathb {Z}}}}}}}$에 대한 평활성의 개념을 구축하기 위해 일반수 체가 사용하는 것이다$.$^[12]

참고 항목

• 고복합수
• 러프 수
• 라운드 넘버
• 스토르머 정리
• 비정상수

참고 및 참조

참고 문헌 목록

• G. 테넨바움, 분석 및 확률론적 수 이론 소개 (AMS, 2015) ISBN 978-0821898543
• A. Granville, 원활한 숫자: MSRI 워크샵의 Proc., 2008

외부 링크

• Weisstein, Eric W. "Smooth Number". MathWorld.

온라인 정수 순서 백과사전(OEIS)은 작은 B를 위한 B-smooth 숫자를 나열한다.

• 2자리 숫자: A000079(2ⁱ)
• 3자리 숫자: A003586(23^ij)
• 5-매끄러운 숫자: A051037(235^ijk)
• 7자리 숫자: A002473(2357^ijkl)
• 11-smooth 숫자: A051038(등...)
• 13자리 숫자: A080197
• 17자리 숫자: A080681
• 19자리 숫자: A080682
• 23자리 숫자: A080683