Número suave

En teoría de números , un número n -suave (o n -friable ) es un entero cuyos factores primos son todos menores o iguales a n . ^{[ 1 ] [ 2 ]} Por ejemplo, un número 7-suave es un número en el que cada factor primo es como máximo 7. Por lo tanto, 49 = 7 ² y 15750 = 2 × 3 ² × 5 ³ × 7 son ambos 7-suaves, mientras que 11 y 702 = 2 × 3 ³ × 13 no son 7-suaves. El término parece haber sido acuñado por Leonard Adleman . ^{[ 3 ]} Los números suaves son especialmente importantes en criptografía , que se basa en la factorización de enteros. Los números 2-suaves son simplemente las potencias de 2 , mientras que los números 5-suaves también se conocen como números regulares .

Un entero positivo se denomina B - suave si ninguno de sus factores primos es mayor que B. Por ejemplo, 1620 tiene factorización prima 2² ^× 3⁴ ^× 5; por lo tanto, 1620 es 5-suave porque ninguno de sus factores primos es mayor que 5. Esta definición incluye números que carecen de algunos de los factores primos más pequeños; por ejemplo, tanto 10 como 12 son 5-suaves, aunque no tengan los factores primos 3 y 5, respectivamente. Todos los números 5-suaves tienen la forma 2a ^× 3b ^× 5c ^, donde a , b y c son enteros no negativos.

Los números 3-suaves también se han llamado "números armónicos", ^{[ 4 ]} aunque ese nombre tiene otros significados más ampliamente utilizados, sobre todo para la suma de los recíprocos de los números naturales . Los números 5-suaves también se llaman números regulares o números de Hamming; ^{[ 5 ]} los números 7-suaves también se llaman números humildes , ^{[ 6 ]} y a veces se llaman altamente compuestos , ^{[ 7 ]} aunque esto entra en conflicto con otro significado de números altamente compuestos .

Cabe señalar que no es necesario que B aparezca entre los factores de un número B -suave. Si el mayor factor primo de un número es p, entonces el número es B -suave para cualquier B ≥ p . En muchos casos, B es primo , pero también se permiten números compuestos . Un número es B -suave si y solo si es p -suave, donde p es el mayor primo menor o igual que B.

Una importante aplicación práctica de los números suaves son los algoritmos de transformada rápida de Fourier (FFT) (como el algoritmo FFT de Cooley-Tukey ), que funciona descomponiendo recursivamente un problema de tamaño n en problemas del tamaño de sus factores. Al usar números B -suaves, se garantiza que los casos base de esta recursión sean primos pequeños, para los cuales existen algoritmos eficientes. (Los primos grandes requieren algoritmos menos eficientes, como el algoritmo FFT de Bluestein ).

Los números que son 5-suaves o regulares juegan un papel especial en las matemáticas babilónicas . ^{[ 8 ]} También son importantes en la teoría musical (véase Límite (música) ), ^{[ 9 ]} y el problema de generar estos números de manera eficiente se ha utilizado como un problema de prueba para la programación funcional . ^{[ 10 ]}

Los números suaves tienen varias aplicaciones en criptografía. ^{[ 11 ]} Si bien la mayoría de las aplicaciones se centran en el criptoanálisis (por ejemplo, los algoritmos de factorización de enteros más rápidos conocidos , como el cribado de campos numéricos general ), la función hash VSH es otro ejemplo de un uso constructivo de la suavidad para obtener un diseño demostrablemente seguro .

En música, una afinación de límite p es el conjunto de intervalos musicales que son razones de dos números p -suaves. ^{[ 12 ]}

Dejar${\displaystyle \Psi (x,y)}$denota el número de enteros suaves de y menores o iguales a x (la función de De Bruijn).

Si el límite de suavidad B es fijo y pequeño, existe una buena estimación para${\displaystyle \Psi (x,B)}$:

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

dónde${\displaystyle \pi (B)}$denota el número de primos menores o iguales a${\displaystyle B}$.

Otherwise, define the parameter u as u = logx / logy: that is, x = y^u. Then,

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

where ${\displaystyle \rho (u)}$ is the Dickman function.

For any k, almost all natural numbers will not be k-smooth.

If ${\displaystyle n=n_{1}n_{2}}$ where ${\displaystyle n_{1}}$ is ${\displaystyle B}$-smooth and ${\displaystyle n_{2}}$ is not (or is equal to 1), then ${\displaystyle n_{1}}$ is called the ${\displaystyle B}$-smooth part of ${\displaystyle n}$. The relative size of the ${\displaystyle x^{1/u}}$-smooth part of a random integer less than or equal to ${\displaystyle x}$ is known to decay much more slowly than ${\displaystyle \rho (u)}$.^[13]

Further, m is called n-powersmooth (or n-ultrafriable) if all prime powers${\displaystyle p^{\nu }}$ dividing m satisfy:

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

For example, 720 (2⁴ × 3² × 5¹) is 5-smooth but not 5-powersmooth (because there are several prime powers greater than 5, e.g.${\displaystyle 3^{2}=9\nleq 5}$ and ${\displaystyle 2^{4}=16\nleq 5}$). It is 16-powersmooth since its greatest prime factor power is 2⁴ = 16. The number is also 17-powersmooth, 18-powersmooth, etc.

Unlike n-smooth numbers, for any positive integer n there are only finitely many n-powersmooth numbers. In fact, the n-powersmooth numbers are exactly the positive divisors of “the least common multiple of 1, 2, 3, …, n” (sequence A003418 in the OEIS), e.g. the 9-powersmooth numbers (also the 10-powersmooth numbers) are exactly the positive divisors of 2520.

n-smooth and n-powersmooth numbers have applications in number theory, such as in Pollard's p − 1 algorithm and ECM. Such applications are often said to work with "smooth numbers," with no n specified; this means the numbers involved must be n-powersmooth, for some unspecified small number n. As n increases, the performance of the algorithm or method in question degrades rapidly. For example, the Pohlig–Hellman algorithm for computing discrete logarithms has a running time of O(n^1/2)—for groups of n-smooth order.

Además, se dice que m es suave sobre un conjunto A si existe una factorización de m donde los factores son potencias de elementos en A. Por ejemplo, dado que 12 = 4 × 3, 12 es suave sobre los conjuntos A ₁ = {4, 3}, A ₂ = {2, 3} y${\displaystyle \mathbb {Z} }$, sin embargo, no sería suave sobre el conjunto A ₃ = {3, 5}, ya que 12 contiene el factor 4 = 2 ² , y ni 4 ni 2 están en A ₃ .

Nótese que el conjunto A no tiene por qué ser un conjunto de factores primos, pero suele ser un subconjunto propio de los primos como se ve en la base de factores del método de factorización de Dixon y la criba cuadrática . Del mismo modo, es lo que utiliza la criba de cuerpos numéricos general para construir su noción de suavidad, bajo el homomorfismo.${\displaystyle \varphi$ :\mathbb {Z} [\theta ]\to \mathbb {Z} /n\mathbb {Z} } . ^{[ 14 ]}

• Número altamente compuesto
• Número aproximado
• Número redondo
• Teorema de Størmer
• Número inusual

• G. Tenenbaum, Introducción a la teoría analítica y probabilística de números , (AMS, 2015) ISBN 978-0821898543
• A. Granville , Números suaves: Teoría computacional de números y más allá , Actas del taller MSRI, 2008

• Weisstein, Eric W. "Número suave" . MathWorld .

La Enciclopedia en Línea de Secuencias de Enteros (OEIS) enumera los números B -suaves para valores pequeños de B :

• Números 2-suaves: A000079 (2 ⁱ )
• 3 números suaves: A003586 (2 ⁱ 3 ^j )
• 5 números suaves: A051037 (2 ⁱ 3 ^j 5 ^k )
• Números suaves de 7: A002473 (2 ⁱ 3 ^j 5 ^k 7 ^l )
• 11 números suaves: A051038 (etc...)
• 13 números suaves: A080197
• 17 números suaves: A080681
• 19 números suaves: A080682
• 23 números suaves: A080683