Número liso

Entero que tiene solo factores primos pequeños

En teoría de números , un número n -suave (o n -friable ) es un número 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 números 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 .

Definición

Un número entero positivo se llama 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 les falten los factores primos 3 y 5, respectivamente. Todos los números 5-suaves tienen la forma 2 ^a × 3 ^b × 5 ^c , donde a , b y c son números enteros no negativos.

Los números 3-lisos también han sido llamados "números armónicos", aunque ese nombre tiene otros significados más ampliamente utilizados. ^[4] Los números 5-lisos también se denominan números regulares o números de Hamming; ^[5] Los números 7-lisos también se denominan números humildes , ^[6] y a veces llamados altamente compuestos , ^[7] aunque esto entra en conflicto con otro significado de números altamente compuestos .

Aquí, nótese que no se requiere que B en sí aparezca entre los factores de un número B -suave. Si el factor primo más grande de un número es p , entonces el número es B -suave para cualquier B ≥ p . En muchos escenarios, 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 primo más grande menor o igual a B.

Aplicaciones

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

Los números 5-suaves o regulares juegan un papel especial en las matemáticas babilónicas . ^[8] También son importantes en la teoría musical (ver 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 la 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 , por ejemplo: Algoritmo de criba de campo de números generales ), la función hash VSH es otro ejemplo de un uso constructivo de la suavidad para obtener un diseño demostrablemente seguro .

Distribución

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

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}}.}$

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

De lo contrario, defina el parámetro u como u  = log  x  / log  y : es decir, x  =  y ^u . Entonces,

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

¿Dónde está la función de Dickman ? ${\displaystyle \rho (u)}$

Para cualquier k , casi todos los números naturales no serán k -suaves.

Si donde es -suave y no es (o es igual a 1), entonces se llama parte -suave de . Se sabe que el tamaño relativo de la parte -suave de un entero aleatorio menor o igual a decae mucho más lentamente que . ^[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)}$

Números de PowerSmooth

Además, m se llama n - potencia suave (o n - ultrafriable ) si todas las potencias primas que dividen a m satisfacen: ${\displaystyle p^{\nu }}$

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

Por ejemplo, 720 (2 ⁴ × 3 ² × 5 ¹ ) es 5-suave pero no 5-potenciasuave (porque hay varias potencias primos mayores que 5, por ejemplo y ). Es 16-potenciasuave ya que su mayor potencia de factor primo es 2 ⁴  = 16. El número también es 17-potenciasuave, 18-potenciasuave, etc. ${\displaystyle 3^{2}=9\nleq 5}$ ${\displaystyle 2^{4}=16\nleq 5}$

A diferencia de los números n -suaves, para cualquier entero positivo n solo hay un número finito de números n -potencias-suaves; de hecho, los números n -potencias-suaves son exactamente los divisores positivos del “ mínimo común múltiplo de 1, 2, 3, …, n ” (secuencia A003418 en la OEIS ), por ejemplo, los números 9-potencias-suaves (también los números 10-potencias-suaves) son exactamente los divisores positivos de 2520.

Los números n -suaves y n -potenciales tienen aplicaciones en la teoría de números, como en el algoritmo p  − 1 de Pollard y en el ECM . A menudo se dice que dichas aplicaciones funcionan con "números suaves", sin n especificado; esto significa que los números involucrados deben ser n -potenciales suaves, para algún pequeño número n no especificado. A medida que s n aumenta, el rendimiento del algoritmo o método en cuestión se degrada rápidamente. Por ejemplo, el algoritmo Pohlig–Hellman para calcular logaritmos discretos tiene un tiempo de ejecución de O ( n ^1/2 )—para grupos de orden n -suave .

Suavizar sobre un conjuntoA

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 , 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 ₃ . ${\displaystyle \mathbb {Z} }$

Obsérvese que el conjunto A no tiene por qué ser un conjunto de factores primos, pero normalmente es 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 . Asimismo, es lo que la criba de cuerpos numéricos generales utiliza para construir su noción de suavidad, bajo el homomorfismo . ^[13] ${\displaystyle \phi :\mathbb {Z} [\theta ]\to \mathbb {Z} /n\mathbb {Z} }$

Véase también

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

Notas y referencias

1. "Números P-Suaves o Números P-Fresibles". GeeksforGeeks . 2018-02-12 . Consultado el 2019-12-12 .
2. Weisstein, Eric W. "Número suave". mathworld.wolfram.com . Consultado el 12 de diciembre de 2019 .
3. Hellman, ME ; Reyneri, JM (1983). "Cálculo rápido de logaritmos discretos en GF ( q )". Avances en criptología – Actas de Crypto 82 . págs. 3–13. doi :10.1007/978-1-4757-0602-4_1. ISBN 978-1-4757-0604-8.
4. Sloane, N. J. A. (ed.). "Secuencia A003586 (números 3-suaves)". La enciclopedia en línea de secuencias de números enteros . Fundación OEIS.
5. "Python: Obtener los números de Hamming hasta un número dado y comprobar si un número dado es un número de Hamming". w3resource . Consultado el 12 de diciembre de 2019 .
6. "Problema H: Números humildes". www.eecs.qmul.ac.uk . Consultado el 12 de diciembre de 2019 .
7. Sloane, N. J. A. (ed.). "Secuencia A002473 (números 7-smooth)". La enciclopedia en línea de secuencias de números enteros . Fundación OEIS.
8. Aaboe, Asger (1965), "Algunas tablas matemáticas seléucidas (recíprocos extendidos y cuadrados de números regulares)", Journal of Cuneiform Studies , 19 (3): 79–86, doi :10.2307/1359089, JSTOR  1359089, MR  0191779, S2CID  164195082.
9. Longuet-Higgins, HC (1962), "Carta a un amigo músico", Music Review (agosto): 244–248.
10. Dijkstra, Edsger W. (1981), Ejercicio de Hamming en SASL (PDF) , Informe EWD792. Originalmente una nota manuscrita que circuló de forma privada.
11. Naccache, David; Shparlinski, Igor (17 de octubre de 2008). "Divisibilidad, suavidad y aplicaciones criptográficas" (PDF) . eprint.iacr.org . arXiv : 0810.2067 . Consultado el 26 de julio de 2017 .F
12. Kim, Taechan; Tibouchi, Mehdi (2015). "Ataques de curvas no válidas en un entorno GLS". En Tanaka, Keisuke; Suga, Yuji (eds.). Avances en seguridad informática e informática: 10.º taller internacional sobre seguridad, IWSEC 2015, Nara, Japón, 26-28 de agosto de 2015, Actas . Apuntes de clase en informática. Vol. 9241. Springer. págs. 41-55. doi :10.1007/978-3-319-22425-1_3.
13. Briggs, Matthew E. (17 de abril de 1998). "Introducción a la criba de campo numérico general" (PDF) . math.vt.edu . Blacksburg, Virginia: Instituto Politécnico y Universidad Estatal de Virginia . Consultado el 26 de julio de 2017 .

Bibliografía

• 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 de números computacionales y más allá, Actas del taller MSRI, 2008

Enlaces externos

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

La Enciclopedia en línea de secuencias de números enteros (OEIS) enumera números B -suaves para B pequeñas :

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