Número liso

En teoría de números, un número liso es un entero que puede factorizarse completamente en números primos pequeños. El término parece haber sido acuñado por Leonard Adleman.^[1]​ Los números lisos son de especial importancia en criptografía basada en factorización.

Definición

Un entero positivo se llama B-liso si ninguno de sus factores primos es mayor que B. Por ejemplo, 1,620 tiene la factorización prima 2² × 3⁴ × 5; por lo tanto, 1,620 es 5-liso pues ninguno de sus factores primos es mayor que 5. Vale la pena notar que esta definición incluye números que carecen de algunos de los primos menores. Por ejemplo, tanto 10 como 12 son 5-liso, no obstante el hecho que les falta los factores primos 3 y 5 respectivamente. Los números 5-liso también se llaman números regulares o números Hamming; los números 7-liso a veces se llaman^{[¿por quién?]} altamente compuestos, aunque esta denominación se confunde con número altamente compuesto.

Nótese que B no tiene que ser un factor primo. Si el mayor de los factores primos de un número es p entonces el número es B-liso para todo B ≥ p. Usualmente B está dado como primo, pero los números compuestos funcionan igualmente. Un número es B-liso si y solo si es p-liso, donde p es el mayor primo menor o igual a B.

Aplicaciones

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

Los números 5-liso o números regulares juegan un papel especial en la matemática babilónica.^[2]​ También son importantes en teoría musical,^[3]​ (véase Límite) y el problema de generar estos números eficientemente ha sido utilizado como problema de prueba en programación funcional.^[4]​

Los números lisos tienen numerosas aplicaciones en criptografía.^[5]​ Aunque la mayoría de las aplicaciones involucran criptoanálisis, la función hash VSH es un ejemplo de uso constructivo de suavidad para obtener un diseño seguro probable.

Distribución

Sea ${\displaystyle \scriptstyle \Psi (x,y)}$ que denota el número de números enteros y-liso menores o iguales a x (la función Bruijn).

Si la cota de suavidad B es fija y pequeña, hay una buena estimación para ${\displaystyle \scriptstyle \Psi (x,B)}$:

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

De otro modo, se define el parámetro u como u = log x / log y: esto es, x = y^u. Entonces,

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

donde ${\displaystyle \scriptstyle \rho (u)}$ es la función Dickman.

Números potencia-lisa

Consiguientemente, m se llama B-potencia-lisa si todas las "potencias" primas ${\displaystyle \scriptstyle p_{i}^{n_{i}}}$ que dividen a m satisfacen:

${\displaystyle p_{i}^{n_{i}}\leq B.\,}$

Por ejemplo, 2⁴3²5¹ es 16-potencia-lisa puesto que su mayor factor de potencia prima es 2⁴ = 16. El número también es 17-potencia-lisa, 18-potencia-lisa, 19-potencia-lisa, etc.

Los números B-liso y B-potencia-lisa tienen aplicaciones en la teoría de números, como en el algoritmo Pollard p − 1. Estas aplicaciones se dice que trabajan con "números lisos", sin B especificado; esto significa que los números involucrados deben ser B-liso para algún pequeño número B no especificado; cuando B se incrementa, la calidad de los resultados del algoritmo o método en cuestión se degradan rápidamente. Por ejemplo, el algoritmo Pohlig–Hellman para calcular logaritmos discretos tiene un tiempo de O(B^1/2) para grupos de orden B-liso.

Notas

1. M. E. Hellman, J. M. Reyneri, "Fast computation of discrete logarithms in GF (q)", in Advances in Cryptology: Proceedings of CRYPTO '82 (eds. D. Chaum, R. Rivest, A. Sherman), New York: Plenum Press, 1983, p. 3–13, online quote at Google Scholar: "Adleman se refiere a enteros que se factorizan completamente en pequeños primos como números "lisos".
2. Aaboe, Asger (1965), «Some Seleucid mathematical tables (extended reciprocals and squares of regular números)», Journal of Cuneiform Studies 19 (3): 79-86, doi:10.2307/1359089, MR 0191779 ..
3. Longuet-Higgins, H. C. (1962), «Letter to a musical friend», Music Review (August): 244-248 ..
4. Dijkstra, Edsger W. (1981), Hamming's exercise in SASL, Report EWD792. Originally a privately-circulated handwitten note ..
5. David Naccache, Igor Shparlinski, "Divisibility, lisoness and Cryptographic Applications", http://eprint.iacr.org/2008/437.pdf

Referencias

• G. Tenenbaum, Introduction to analytic and probabilistic number theory, (CUP, 1995) ISBN 0-521-41261-7
• A. Granville, Smooth numbers: Computational number theory and beyond, Proc. of MSRI workshop, 2004

Enlaces externos

• Weisstein, Eric W. «liso Number». En Weisstein, Eric W, ed. MathWorld (en inglés). Wolfram Research. 

La Enciclopedia electrónica de secuencias de enteros (OEIS) lista números B-liso para B pequeños:

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