número suave

Entero que tiene sólo 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 que n . ^{[1] [2]} Por ejemplo, un número 7 liso es un número cuyos factores primos son como máximo 7, por lo que 49 = 7 ² y 15750 = 2 × 3 ² × 5 ³ × 7 son ambos 7 lisos, mientras que 11 y 702 = 2 × 3 ³ × 13 no son 7 lisos. El término parece haber sido acuñado por Leonard Adleman . ^[3] Los números fluidos son especialmente importantes en criptografía , que se basa en la factorización de números enteros. Los números 2 suaves son solo las potencias de 2 , mientras que los números 5 suaves 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, 1,620 tiene factorización prima 2 ² × 3 ⁴ × 5; por lo 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 10 como 12 son 5 suaves, aunque omiten los factores primos 3 y 5, respectivamente. Todos los números 5 lisos tienen la forma 2 ^a × 3 ^b × 5 ^c , donde a , b y c son números enteros no negativos.

Los números de 3 suaves también han sido llamados "números armónicos", aunque ese nombre tiene otros significados más utilizados. ^[4] 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 llaman números humildes , ^[6] y a veces se les llama altamente compuestos , ^[7] aunque esto entra en conflicto con otro significado de números altamente compuestos .

Here, note that B itself is not required to appear among the factors of a B-smooth number. If the largest prime factor of a number is p then the number is B-smooth for any B ≥ p. In many scenarios B is prime, but composite numbers are permitted as well. A number is B-smooth if and only if it is p-smooth, where p is the largest prime less than or equal to B.

Applications

An important practical application of smooth numbers is the fast Fourier transform (FFT) algorithms (such as the Cooley–Tukey FFT algorithm), which operates by recursively breaking down a problem of a given size n into problems the size of its factors. By using B-smooth numbers, one ensures that the base cases of this recursion are small primes, for which efficient algorithms exist. (Large prime sizes require less-efficient algorithms such as Bluestein's FFT algorithm.)

5-smooth or regular numbers play a special role in Babylonian mathematics.^[8] They are also important in music theory (see Limit (music)),^[9] and the problem of generating these numbers efficiently has been used as a test problem for functional programming.^[10]

Smooth numbers have a number of applications to cryptography.^[11] While most applications center around cryptanalysis (e.g. the fastest known integer factorization algorithms, for example: General number field sieve algorithm), the VSH hash function is another example of a constructive use of smoothness to obtain a provably secure design.

Distribution

Let ${\displaystyle \Psi (x,y)}$ denote the number of y-smooth integers less than or equal to x (the de Bruijn function).

If the smoothness bound B is fixed and small, there is a good estimate for ${\displaystyle \Psi (x,B)}$:

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

where ${\displaystyle \pi (B)}$ denotes the number of primes less than or equal to ${\displaystyle B}$.

Otherwise, define the parameter u as u = log x / log y: 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.

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

Si donde es suave y no lo 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 fluidos

Además, m se llama n - powersmooth (o n - ultrafriable ) si todos los poderes primos que dividen m satisfacen: ${\displaystyle p^{\nu }}$

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

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

A diferencia de los n -números suaves, para cualquier entero positivo n sólo hay un número finito de n -números suaves; de hecho, los n -números 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 de 9 potencias suaves (también los números de 10 potencias suaves) son exactamente los divisores positivos de 2520.

Los números n -suaves y n -powersmooth 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 n especificada; esto significa que los números involucrados deben ser n -powersmooth, para algún número pequeño no especificado n. A medida que n aumenta, el rendimiento del algoritmo o método en cuestión se degrada rápidamente. Por ejemplo, el algoritmo de Pohlig-Hellman para calcular logaritmos discretos tiene un tiempo de ejecución de O ( n ^1/2 ), para grupos de n -orden suave .

Alise sobre un conjunto A

Además, se dice que m es suave en 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} }$

Tenga en cuenta que el conjunto A no tiene por qué ser un conjunto de factores primos, pero suele ser un subconjunto adecuado 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 utiliza la criba general de campos numéricos para construir su noción de suavidad, bajo el homomorfismo . ^[13] ${\displaystyle \phi :\mathbb {Z} [\theta ]\to \mathbb {Z} /n\mathbb {Z} }$

Ver también

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

notas y referencias

1. "Números P-suaves o Número P-friable". Geeks para Geeks . 2018-02-12 . Consultado el 12 de diciembre de 2019 .
2. Weisstein, Eric W. "Número suave". mathworld.wolfram.com . Consultado el 12 de diciembre de 2019 .
3. Hellman, YO ; 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, Nueva Jersey (ed.). "Secuencia A003586 (3 números suaves)". La enciclopedia en línea de secuencias enteras . Fundación OEIS.
5. "Python: obtenga los números de Hamming hasta un número determinado y también verifique si un número determinado es un número de Hamming". w3recurso . 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, Nueva Jersey (ed.). "Secuencia A002473 (7 números suaves)". La enciclopedia en línea de secuencias enteras . 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 musical", Music Review (agosto): 244–248.
10. Dijkstra, Edsger W. (1981), Ejercicio de Hamming en SASL (PDF) , Informe EWD792. Originalmente una nota manuscrita de circulación 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". IWSEC 2015 .
13. 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 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á, Proc. del taller de MSRI, 2008

enlaces externos

• Weisstein, Eric W. "Número suave". MundoMatemático .

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

• Números 2 lisos: A000079 (2 ⁱ )
• Números de 3 suaves: A003586 (2 ⁱ 3 ^j )
• Números de 5 suaves: 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