滑らかな数

数論において、n滑らかな数（またはn壊れやすい数）は、素因数が全てn以下である整数である。^{[1] [2]}例えば、 7 滑らかな数とは、全ての素因数が最大でも 7 である数である。したがって、 49 = 7 ²と 15750 = 2 × 3 ² × 5 ³ × 7 は両方とも 7 滑らかであるが、 11 と 702 = 2 × 3 ^{3 × 13 は 7 滑らかではない。この用語は}、レナード・エイドルマンによって造られたと思われる。^[3]滑らかな数は、整数の因数分解に依存する暗号において特に重要である。 2 滑らかな数は単に2 の累乗であり、 5 滑らかな数は通常の数としても知られている。

正の 整数がBより大きくない素因数を持つ場合、その整数はB平滑と呼ばれます。たとえば、 1,620 は 2 ² × 3 ⁴ × 5 という素因数分解ができます。したがって、 1,620 は 5 より大きい素因数がないので 5 平滑です。この定義には、いくつかの小さい素因数が欠けている数も含まれます。たとえば、 10 と 12 は、それぞれ素因数 3 と 5 が欠けていますが、どちらも 5 平滑です。すべての 5 平滑数は 2 ^a × 3 ^b × 5 ^cの形式です。ここで、a、b 、およびc は負でない整数です。

3-滑らかな数は「調和数」とも呼ばれるが、この名前にはより広く使われている他の意味がある。^[4] 5-滑らかな数は、通常数またはハミング数とも呼ばれる。^[5] 7-滑らかな数は、謙虚数とも呼ばれ、^[6]高度に合成された数と呼ばれることもあるが、^[7]これは高度に合成された数の別の意味と矛盾する。

ここで、B自体はB滑らかな数の因数として現れる必要はないことに注意してください。ある数の最大の素因数がpである場合、その数はB ≥ pのいずれに対してもB滑らかです。多くのシナリオではBは素数ですが、合成数も許可されています。数がB滑らかであるのは、それがp滑らかである場合のみです。ここで、 pはB以下の最大の素数です。

滑らかな数の重要な実用的応用は、高速フーリエ変換(FFT) アルゴリズム ( Cooley-Tukey FFT アルゴリズムなど) です。これは、指定されたサイズnの問題をその因数のサイズの問題に再帰的に分解することによって機能します。B 滑らかな数を使用することで、この再帰の基本ケースが小さな素数であることが保証され、効率的なアルゴリズムが存在します。 (大きな素数サイズには、 Bluestein の FFT アルゴリズムなどの効率の低いアルゴリズムが必要です。)

5-滑らかな数や正則数はバビロニア数学において特別な役割を果たしている。^[8]また、音楽理論においても重要であり（「極限（音楽） 」を参照）、^[9]これらの数を効率的に生成する問題は関数型プログラミングのテスト問題として使われてきた。^[10]

滑らかな数は暗号化に多くの応用がある。^{[11]ほとんどの応用は}暗号解読（例えば、最も高速な既知の整数因数分解アルゴリズム、例えば一般数体ふるいアルゴリズム）に集中しているが、 VSHハッシュ関数は滑らかさを建設的に利用して証明可能な安全性の設計を得るもう一つの例である。

をx以下のy滑らかな整数の数(de Bruijn 関数) とします。${\displaystyle \Psi (x,y)}$

滑らかさの境界Bが固定かつ小さい場合、 の良い推定値が得られます。 ${\displaystyle \Psi (x,B)}$

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

ここで、 は以下の素数の数を表します。 ${\displaystyle \pi (B)}$ ${\displaystyle B}$

それ以外の場合は、パラメータuをu  = log  x  / log  y、つまりx  =  y ^uと定義します。すると、

${\displaystyle \Psi (x,y)=x\cdot \rho (u)+O\left({\frac {x}{\log y}}\right)}$

ここで、Dickman 関数です。 ${\displaystyle \rho (u)}$

任意のkに対して、ほとんどすべての自然数はk滑らかではありません。

が-平滑で がそうでない場合（または が 1 に等しい場合）、 はの -平滑部分と呼ばれます。より小さいか等しいランダムな整数の -平滑部分の相対的な大きさはよりもはるかにゆっくりと減少することが知られています。^[12]${\displaystyle n=n_{1}n_{2}}$${\displaystyle n_{1}}$${\displaystyle B}$${\displaystyle n_{2}}$${\displaystyle n_{1}}$${\displaystyle B}$${\displaystyle n}$${\displaystyle x^{1/u}}$${\displaystyle x}$${\displaystyle \rho (u)}$

さらに、m を割り切るすべての素数累乗が次を満たす場合、 m はn -累乗平滑(またはn -超脆性)であるといいます。 ${\displaystyle p^{\nu }}$

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

たとえば、720 (2 ⁴ × 3 ² × 5 ¹ ) は 5 滑らかですが、5 べき乗滑らかではありません ( や など、5 より大きい素因数累乗が複数あるため)。最大の素因数累乗は 2 ⁴ = 16なので、16 べき乗滑らかです。 この数は 17 べき乗滑らか、18 べき乗滑らかなどでもあります。 ${\displaystyle 3^{2}=9\nleq 5}$${\displaystyle 2^{4}=16\nleq 5}$

n滑らかな数と異なり、任意の正の整数nに対してnべき滑らかな数は有限個しか存在せず、実際、nべき滑らかな数は「1、2、3、…、nの最小公倍数」( OEISのシーケンスA003418 ) の正の約数とまったく同じです。たとえば、9 べき滑らかな数 (10 べき滑らかな数も) は 2520 の正の約数とまったく同じです。

n滑らかな数とnべき滑らかな数は、ポラードのp  − 1 アルゴリズムやECMなどの数論に応用されています。このような応用は、 nが指定されていない「滑らかな数」で機能すると言われることがよくあります。つまり、関係する数は、指定されていない小さな数nに対してnべき滑らかでなければなりません。nが増加すると、問題のアルゴリズムまたは方法のパフォーマンスは急速に低下します。たとえば、離散対数を計算するPohlig–Hellman アルゴリズムの実行時間は、 n滑らかな順序のグループの場合、 O ( n ^1/2 )です。

さらに、mの因数分解が存在し、因数がAの要素の累乗である場合、 m は集合 A上で滑らかであるといわれます。たとえば、 12 = 4 × 3 なので、 12 は集合A ₁ = {4, 3}、A ₂ = {2, 3}、および上で滑らかです。しかし、 12 には因数 4 = 2 ²が含まれ、 4 も 2 もA _{3には含まれていないため、集合}A ₃ = {3, 5}上では滑らかではありません。 ${\displaystyle \mathbb {Z} }$

集合Aは素因数の集合である必要はないが、ディクソン因数分解法の因数基数や二次ふるいに見られるように、典型的には素数の適切な部分集合であることに注意されたい。同様に、一般数体ふるいは準同型の下で滑らかさの概念を構築するためにこれを使用する。^[13] ${\displaystyle \phi :\mathbb {Z} [\theta ]\to \mathbb {Z} /n\mathbb {Z} }$

• 高度に合成された数
• 大まかな数字
• ラウンドナンバー
• シュテルマーの定理
• 異常な数字

• G. テネンバウム『解析的および確率的数論入門』（AMS、2015年）ISBN 978-0821898543 
• A. Granville、「滑らかな数：計算数論とその先」、MSRIワークショップ議事録、2008年

• Weisstein、Eric W.「滑らかな数」。MathWorld。

オンライン整数列百科事典( OEIS)には、小さなBに対するB滑らかな数がリストされています。

• 2 滑らかな数: A000079 (2 ⁱ )
• 3つの滑らかな数: A003586 (2 ⁱ 3 ^j )
• 5つの滑らかな数字: A051037 (2 ⁱ 3 ^j 5 ^k )
• 7 滑らかな数字: A002473 (2 ⁱ 3 ^j 5 ^k 7 ^l )
• 11 個の滑らかな数字: A051038 (など)
• 13 滑らかな数字: A080197
• 17 滑らかな数字: A080681
• 19 滑らかな数字: A080682
• 23 滑らかな数字: A080683