Número liso

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.

Contenido

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 22 × 34 × 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 Bp. 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 provable.

Distribución

Sea \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 \scriptstyle\Psi(x,B):

 \Psi(x,B) \sim  \frac{1}{\pi(B)!} \prod_{p\le B}\frac{\log x}{\log p}.

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

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

donde \scriptstyle\rho(u) es la función Dickman.

Números potencia-lisa

Consiguientemente, m se llama B-potencia-lisa si todas las "potencias" primas \scriptstyle p_i^{n_i} que dividen a m satisfacen:

p_i^{n_i} \leq B.\,

Por ejemplo, 243251 es 16-potencia-lisa puesto que su mayor factor de potencia prima es es 24 = 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 Pohlig–Hellman para calcular logaritmos discretos tiene un tiempo de O(B1/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, MR0191779 .
  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, http://www.cs.utexas.edu/users/EWD/ewd07xx/EWD792.PDF .
  5. David Naccache, Igor Shparlinski, "Divisibility, lisoness and Cryptographic Applications", http://eprint.iacr.org/2008/437.pdf

Referencias

Enlaces externos

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


Wikimedia foundation. 2010.

Игры ⚽ Поможем написать реферат

Mira otros diccionarios:

  • Actina — G (código PDB …   Wikipedia Español

  • Citoplasma — Dibujo esquemático de una célula con sus respectivos orgánulos. (1) Nucléolo (2) Núcleo celular (3) Ribosoma ( …   Wikipedia Español

  • Razas de canario — Saltar a navegación, búsqueda Canario El canario (Serinus canaria) es, sin lugar a ningún tipo de dudas, el pájaro doméstico de mayor popularidad en todo el mundo, al punto tal que, de tener un área de dispersión en estado salvaje bastante… …   Wikipedia Español

  • Monetario clásico de la República Oriental del Uruguay — El Monetario Clásico de la República Oriental del Uruguay comprende las acuñaciones realizadas por la República Oriental del Uruguay entre los años 1839 y 1855 en territorio nacional. Estas acuñaciones fueron realizadas completamente dentro de la …   Wikipedia Español

  • Cerebelo — Saltar a navegación, búsqueda Cerebelo Un encéfalo humano, con el cerebelo marcado en morado Im …   Wikipedia Español

  • Flujo sanguíneo — Saltar a navegación, búsqueda Contenido 1 Definición. 2 Introducción 2.1 Valores normales en el humano 2.2 Índice c …   Wikipedia Español

  • Tesoro de Villena — Conjunto del Tesoro de Villena. Conjunto del Tesoro de Villena y el …   Wikipedia Español

  • PDE3 — Fosfodiesterasa 3A Otros nombres Fosfodiesterasa A inhibida por el cGMP HUGO 8778 Símbolo PDE3A …   Wikipedia Español

  • Tabla — (Del lat. tabula.) ► sustantivo femenino 1 CARPINTERÍA Pieza de madera plana, más larga que ancha y de poco grosor: ■ él mismo puede hacer la mesa con unas tablas. SINÓNIMO listón 2 Pieza plana y de poco grosor de un material rígido: ■ la… …   Enciclopedia Universal

  • Gramática del pipil — «Gramática del náhuat» redirige aquí. Para otras acepciones, véase Gramática del náhuat (desambiguación). Gramática pipil se refiere al conjunto de reglas y principios que regulan el uso del idioma pipil. Este artículo muestra un esquema… …   Wikipedia Español

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”