En la teoría de números , un n -smooth (o n -friable ) número es un número entero cuyo factores prime son todos menos de o igual a n . [1] [2] [3] Por ejemplo, un número 7-suave es un número cuyo factor primo es como máximo 7, por lo que 49 = 7 2 y 15750 = 2 × 3 2 × 5 3 × 7 son ambos 7- suave, mientras que 11 y 702 = 2 × 3 3 × 13 no son 7 suaves. El término parece haber sido acuñado por Leonard Adleman . [4] Los números suaves son especialmente importantes encriptografía , que se basa en la factorización de números enteros. Los números de 2 suaves son solo las potencias de 2 , mientras que los números de 5 suaves se conocen como números regulares .
Definición
Un positivo entero se llama B - suavizar si ninguno de sus factores primos es mayor que B . Por ejemplo, 1.620 tiene factorización prima 2 2 × 3 4 × 5; por tanto, 1,620 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 el 10 como el 12 son 5 suaves, aunque omiten los factores primos 3 y 5, respectivamente. Todos los números de 5-lisas son de la forma 2 un × 3 b × 5 c , donde un , b y c son números enteros no negativos.
Los números de 5 suaves también se denominan números regulares o números de Hamming; [5] Los números 7-suaves también se denominan números humildes , [6] ya veces se los llama altamente compuestos , [7] aunque esto entra en conflicto con otro significado de números altamente compuestos .
Aquí, tenga en cuenta que no se requiere que B 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 -smooth si y sólo si es p -smooth, donde p es el primer grande menor o igual a B .
Aplicaciones
Una aplicación práctica importante de los números suaves son los algoritmos de transformada rápida de Fourier (FFT) (como el algoritmo Cooley-Tukey FFT ), que opera descomponiendo recursivamente un problema de un tamaño dado n en problemas del tamaño de sus factores. Al usar números B -smooth, se asegura que los casos base de esta recursividad sean pequeños números primos, para los cuales existen algoritmos eficientes. (Los tamaños 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 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 para 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 tamiz de campo numérico general ), la función hash VSH es otro ejemplo de un uso constructivo de la suavidad para obtener un diseño comprobablemente seguro .
Distribución
Dejar denotar el número de y -enteros suaves menores o iguales ax (la función de Bruijn).
Si el límite de suavidad B es fijo y pequeño, hay una buena estimación de:
dónde denota el número de primos menores o iguales que .
De lo contrario, defina el parámetro u como u = log x / log y : es decir, x = y u . Luego,
dónde es la función de Dickman .
El tamaño medio de la parte lisa de un número determinado se conoce como , y se sabe que se descompone mucho más lentamente que . [12]
Para cualquier k , casi todos los números naturales no serán k- suaves.
Números de Powersmooth
Además, m se llama B - powersmooth (o B - ultrafriable ) si todos los poderes principales dividir m satisface:
Por ejemplo, 720 (2 4 × 3 2 × 5 1 ) es 5-suave pero no 5-powersmooth (porque hay varios poderes primos mayores que 5, p . Ej. y ). Es 16-powersmooth ya que su mayor potencia de factor primo es 2 4 = 16. El número también es 17-powersmooth, 18-powersmooth, etc.
Los números B- suaves y B -poderes suaves tienen aplicaciones en la teoría de números, como en el algoritmo p -1 de Pollard y ECM . A menudo se dice que estas aplicaciones funcionan con "números suaves", sin B especificado; esto significa que los números involucrados deben ser B - potencias suaves, para algunos números pequeños no especificados B. A s B aumenta, el rendimiento del algoritmo o método en cuestión se degrada rápidamente. Por ejemplo, el algoritmo de Pohlig-Hellman para el cálculo de logaritmos discretos tiene un tiempo de ejecución de O ( B 1/2 ) -para grupos de B -smooth orden .
Suavizar sobre un conjunto A
Por otra parte, m se dice que ser lisa sobre un conjunto A si existe una factorización de m donde los factores son potencias de los elementos en A . Por ejemplo, dado que 12 = 4 × 3, 12 es uniforme sobre los conjuntos A 1 = {4, 3}, A 2 = {2, 3} y, sin embargo, no sería uniforme sobre el conjunto A 3 = {3, 5}, ya que 12 contiene el factor 4 = 2 2 , que no está en A 3 .
Tenga en cuenta que el conjunto A no tiene que ser un conjunto de factores primos, pero normalmente es un subconjunto adecuado de los números primos como se ve en la base de factores del método de factorización de Dixon y el tamiz cuadrático . Asimismo, es lo que utiliza el tamiz de campo numérico general para construir su noción de suavidad, bajo el homomorfismo . [13]
Ver también
- Número altamente compuesto
- Número aproximado
- Número redondeado
- Teorema de Størmer
- Número inusual
notas y referencias
- ^ "El glosario definitivo de jerga matemática superior - suave" . Bóveda de matemáticas . 2019-08-01 . Consultado el 12 de diciembre de 2019 .
- ^ "Números P-Suaves o Número P-friable" . GeeksforGeeks . 2018-02-12 . Consultado el 12 de diciembre de 2019 .
- ^ Weisstein, Eric W. "Número suave" . mathworld.wolfram.com . Consultado el 12 de diciembre de 2019 .
- ^ Hellman, ME ; Reyneri, JM (1983). Cálculo rápido de logaritmos discretos en GF (q) . Avances en criptología: Actas de CRYPTO '82 (Eds. D. Chaum, R. Rivest, A. Sherman) . págs. 3-13. doi : 10.1007 / 978-1-4757-0602-4_1 . ISBN 978-1-4757-0604-8.
- ^ "Python: Obtenga los números de Hamming hasta un número dado y verifique si un número dado es un número de Hamming" . w3resource . Consultado el 12 de diciembre de 2019 .
- ^ "Problema H: números humildes" . www.eecs.qmul.ac.uk . Consultado el 12 de diciembre de 2019 .
- ^ Sloane, N. J. A. (ed.). "Secuencia A002473 (7 números suaves)" . La enciclopedia en línea de secuencias de enteros . Fundación OEIS.
- ^ 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.
- ^ Longuet-Higgins, HC (1962), "Carta a un amigo musical", Music Review (agosto): 244–248.
- ^ Dijkstra, Edsger W. (1981), ejercicio de Hamming en SASL (PDF) , Informe EWD792. Originalmente una nota manuscrita de circulación privada.
- ^ Naccache, David; Shparlinski, Igor (17 de octubre de 2008). "Divisibilidad, suavidad y aplicaciones criptográficas" (PDF) . eprint.iacr.org . Consultado el 26 de julio de 2017 .F
- ^ Tanaka, Keisuke; Suga, Yuji (20 de agosto de 2015). Advances in Information and Computer Security: 10th International Workshop on Security, IWSEC 2015, Nara, Japón, 26-28 de agosto de 2015, Actas . Saltador. págs. 49–51. ISBN 9783319224251.
- ^ Briggs, Matthew E. (17 de abril de 1998). "Introducción al tamiz 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 de números analítica y probabilística , (AMS, 2015) ISBN 978-0821898543
- A. Granville , Números suaves: teoría de números computacional y más allá , Proc. del taller MSRI, 2008
enlaces externos
- Weisstein, Eric W. "Número suave" . MathWorld .
La Enciclopedia en línea de secuencias de enteros (OEIS) enumera B -números suaves para B pequeños :
- 2 números suaves: A000079 (2 i )
- 3 números suaves: A003586 (2 i 3 j )
- 5 números suaves: A051037 (2 i 3 j 5 k )
- 7 números suaves: A002473 (2 i 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