Número suave

En teoría de números, un número n-suave é un número enteiro cuxos factores primos son todos menores ou iguais a n.^[1][2] Por exemplo, un número 7-suave é un número cuxos factores primos son como máximo 7, polo que 49 = 7 ² e 15750 = 2 × 3 ² × 5 ³ × 7 son ambos 7-suaves, mentres que 11 e 702 = 2 × 3 ³ × 13 non son 7-suaves. O termo parece ser que foi acuñado por Leonard Adleman.^[3] Os números suaves son especialmente importantes na criptografía, que depende da factorización de números enteiros. Os números 2-suaves son só as potencias de 2, mentres que os números 5-suaves son coñecidos como números regulares.

Definición

Un número enteiro positivo chámase B-suave se ningún dos seus factores primos é maior que B .

Por exemplo, 1620 ten factorización prima 2² × 3⁴ × 5, polo tanto, 1620 é 5-suave porque ningún dos seus factores primos é maior que 5. Esta definición inclúe números que carecen dalgúns dos factores primos máis pequenos; por exemplo, tanto 10 como 12 son 5-suaves, aínda que perden os factores primos 3 e 5, respectivamente. Todos os números 5-suaves teñen a forma 2^a × 3^b × 5^c, onde a, b e c son enteiros non negativos.

Aquí, teña en conta que B en si non está obrigado a aparecer entre os factores dun número B-suave. En moitos escenarios B é primo, mais tamén se permiten números compostos. Un número é B-suave se e só se é p-suave, onde p é o maior primo menor ou igual que B.

Aplicación

Unha aplicación práctica importante dos números suaves son os algoritmos da transformada rápida de Fourier (FFT) (como o algoritmo FFT de Cooley-Tukey ), que operan descompoñendo recursivamente un problema dun tamaño n dado en problemas do tamaño dos seus factores. Usando números B-suaves, asegúrase de que os casos base desta recursividade sexan números primos pequenos, para os que existen algoritmos eficientes. (Os tamaños primos grandes requiren algoritmos menos eficientes como o algoritmo FFT de Bluestein).

Os números n-suaves e n-potencia suave (ver abaixo) teñen aplicacións na teoría de números, como no algoritmo p-1 de Pollard e no ECM (factorización de curvas elípticas de Lenstra).

Números potencia suave

Temos tamén que m se chama n-potencia suave se todas as potencias primas ${\displaystyle p^{\nu }}$ dividindo m satisfan:

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

Por exemplo, 720 (2 ⁴ × 3 ² × 5 ¹) é 5-suave mais non 5-potencia suave (porque hai varias potencias primas superiores a 5, p. ex. ${\displaystyle 3^{2}=9\nleq 5}$ e ${\displaystyle 2^{4}=16\nleq 5}$ ).No entanto si que é 16-potencia suave xa que a súa maior potencia do factor primo é 2⁴ = 16.

Núemros suaves sobre un conxunto A

Tamén se di que m é suave sobre un conxunto A se existe unha factorización de m onde os factores son potencias dos elementos en A. Por exemplo, xa que 12 = 4 × 3, temos que 12 é suave sobre os conxuntos A₁ = {4, 3}, A₂ = {2, 3}, no entanto, non sería suave sobre o conxunto A₃ = {3, 5}, xa que 12 contén o factor 4 = 2 ², e nin 4 nin 2 están en A₃.

Teña en conta que o conxunto A non ten que ser un conxunto de factores primos, pero normalmente é un subconxunto propio dos primos como se ve na base de factores do método de factorización de Dixon e na criba cadrática. Así mesmo, é o concepto que usa a criba xeral do corpo de números (GNFS), baixo o homomorfismo ${\displaystyle \phi :\mathbb {Z} [\theta ]\to \mathbb {Z} /n\mathbb {Z} }$.^[4]

Notas

1. "P-Smooth Numbers or P-friable Number". GeeksforGeeks (en inglés). 2018-02-12. Consultado o 2019-12-12. 
2. Weisstein, Eric W. "Smooth Number". mathworld.wolfram.com (en inglés). Consultado o 2019-12-12. 
3. Hellman, M. E.; Reyneri, J. M. (1983). "Fast Computation of Discrete Logarithms in GF (q)". Advances in Cryptology – Proceedings of Crypto 82. pp. 3–13. ISBN 978-1-4757-0604-8. doi:10.1007/978-1-4757-0602-4_1. 
4. Briggs, Matthew E. (17 April 1998). "An Introduction to the General Number Field Sieve" (PDF). math.vt.edu. Blacksburg, Virginia: Virginia Polytechnic Institute and State University. Arquivado dende o orixinal (PDF) o 09 de decembro de 2017. Consultado o 26 July 2017. 

Véxase tamén

Bibliografía

• G. Tenenbaum, Introduction to analytic and probabilistic number theory, (AMS, 2015) ISBN 978-0821898543
• A. Granville, Smooth numbers: Computational number theory and beyond, Proc. of MSRI workshop, 2008

Outros artigos

• Teorema de Størmer.

Ligazóns externas

• Weisstein, Eric W. "Smooth Number". MathWorld. 

A OEIS, On-Line Encyclopedia of Integer Sequences, lista números B-suaves para pequenos Bs:

• 2-smooth numbers: A000079 (2ⁱ)
• 3-smooth numbers: A003586 (2ⁱ3^j)
• 5-smooth numbers: A051037 (2ⁱ3^j5^k)
• 7-smooth numbers: A002473 (2ⁱ3^j5^k7^l)
• 11-smooth numbers: A051038 (etc...)
• 13-smooth numbers: A080197
• 17-smooth numbers: A080681
• 19-smooth numbers: A080682
• 23-smooth numbers: A080683