Función despreciable

En matemáticas, una función despreciable es una función tal que para cada entero positivo c existe un entero N _c tal que para todo x  >  N _c , ${\displaystyle \mu :\mathbb {N} \to \mathbb {R} }$

${\displaystyle |\mu (x)|<{\frac {1}{x^{c}}}.}$

De manera equivalente, también podemos utilizar la siguiente definición. Una función es despreciable si para cada polinomio positivo poly(·) existe un entero N _poly  > 0 tal que para todo x  >  N _poly ${\displaystyle \mu :\mathbb {N} \to \mathbb {R} }$

${\displaystyle |\mu (x)|<{\frac {1}{\operatorname {poly} (x)}}.}$

Historia

El concepto de insignificancia puede remontarse a modelos sólidos de análisis. Aunque los conceptos de " continuidad " e " infinitesimal " se volvieron importantes en matemáticas durante la época de Newton y Leibniz (década de 1680), no se definieron bien hasta fines de la década de 1810. La primera definición razonablemente rigurosa de continuidad en el análisis matemático se debió a Bernard Bolzano , quien escribió en 1817 la definición moderna de continuidad. Más tarde, Cauchy , Weierstrass y Heine también definieron lo siguiente (con todos los números en el dominio de los números reales ): ${\displaystyle \mathbb {R} }$

( Función continua ) Una función es continua en si para cada , existe un número positivo tal que implica ${\displaystyle f:\mathbb {R} {\rightarrow }\mathbb {R} }$ ${\displaystyle x=x_{0}}$ ${\displaystyle \varepsilon >0}$ ${\displaystyle \delta >0}$ ${\displaystyle |x-x_{0}|<\delta }$ ${\displaystyle |f(x)-f(x_{0})|<\varepsilon .}$

Esta definición clásica de continuidad se puede transformar en la definición de insignificancia en unos pocos pasos modificando los parámetros utilizados en la definición. En primer lugar, en el caso de , debemos definir el concepto de " función infinitesimal ": ${\displaystyle x_{0}=\infty }$ ${\displaystyle f(x_{0})=0}$

( Infinitesimal ) Una función continua es infinitesimal (ya que tiende al infinito) si para cada existe tal que para todo ${\displaystyle \mu :\mathbb {R} \to \mathbb {R} }$ ${\displaystyle x}$ ${\displaystyle \varepsilon >0}$ ${\displaystyle N_{\varepsilon }}$ ${\displaystyle x>N_{\varepsilon }}$

${\displaystyle |\mu (x)|<\varepsilon \,.}$^{[ cita requerida ]}

A continuación, reemplazamos por las funciones donde o por donde es un polinomio positivo . Esto nos lleva a las definiciones de funciones despreciables que se dan al principio de este artículo. Dado que las constantes se pueden expresar como con un polinomio constante, esto demuestra que las funciones infinitesimales son un superconjunto de funciones despreciables. ${\displaystyle \varepsilon >0}$ ${\displaystyle 1/x^{c}}$ ${\displaystyle c>0}$ ${\displaystyle 1/\operatorname {poly} (x)}$ ${\displaystyle \operatorname {poly} (x)}$ ${\displaystyle \varepsilon >0}$ ${\displaystyle 1/\operatorname {poly} (x)}$

Uso en criptografía

En la criptografía moderna basada en la complejidad , un esquema de seguridad es demostrablemente seguro si la probabilidad de falla de seguridad (por ejemplo, invertir una función unidireccional , distinguir bits pseudoaleatorios criptográficamente fuertes de bits verdaderamente aleatorios) es insignificante en términos de la entrada = longitud de la clave criptográfica . De ahí la definición en la parte superior de la página porque la longitud de la clave debe ser un número natural. ${\displaystyle x}$ ${\displaystyle n}$ ${\displaystyle n}$

Sin embargo, la noción general de insignificancia no requiere que el parámetro de entrada sea la longitud de la clave . De hecho, puede ser cualquier métrica predeterminada del sistema y el análisis matemático correspondiente ilustraría algunos comportamientos analíticos ocultos del sistema. ${\displaystyle x}$ ${\displaystyle n}$ ${\displaystyle x}$

La formulación recíproca de polinomios se utiliza por la misma razón que la acotación computacional se define como el tiempo de ejecución de un polinomio: tiene propiedades matemáticas de cierre que la hacen manejable en el contexto asintótico (ver #Propiedades de cierre). Por ejemplo, si un ataque logra violar una condición de seguridad con una probabilidad insignificante, y el ataque se repite una cantidad polinómica de veces, la probabilidad de éxito del ataque general sigue siendo insignificante.

En la práctica, es posible que queramos tener funciones más concretas que limiten la probabilidad de éxito del adversario y elegir un parámetro de seguridad lo suficientemente grande como para que esta probabilidad sea menor que un cierto umbral, digamos 2 ⁻¹²⁸ .

Propiedades del cierre

Una de las razones por las que se utilizan funciones despreciables en los fundamentos de la criptografía basada en la teoría de la complejidad es que obedecen a propiedades de cierre. ^[1] Específicamente,

1. Si son despreciables, entonces la función es despreciable. ${\displaystyle f,g:\mathbb {N} \to \mathbb {R} }$ ${\displaystyle x\mapsto f(x)+g(x)}$
2. Si es despreciable y es cualquier polinomio real, entonces la función es despreciable. ${\displaystyle f:\mathbb {N} \to \mathbb {R} }$ ${\displaystyle p}$ ${\displaystyle x\mapsto p(x)\cdot f(x)}$

Por el contrario , si no es despreciable, entonces ninguno lo es para ningún polinomio real . ${\displaystyle f:\mathbb {N} \to \mathbb {R} }$ ${\displaystyle x\mapsto f(x)/p(x)}$ ${\displaystyle p}$

Ejemplos

• ${\displaystyle n\mapsto a^{-n}}$es insignificante para cualquier . ${\displaystyle a\geq 2}$
• ${\displaystyle f(n)=3^{-{\sqrt {n}}}}$es insignificante.
• ${\displaystyle f(n)=n^{-\log n}}$es insignificante.
• ${\displaystyle f(n)=(\log n)^{-\log n}}$es insignificante.
• ${\displaystyle f(n)=2^{-c\log n}}$no es despreciable, por positivo . ${\displaystyle c}$

Supongamos que tomamos el límite como : ${\displaystyle n>0}$ ${\displaystyle n\to \infty }$

Insignificante :

• ${\displaystyle f(n)=1/x^{n/2}}$
• ${\displaystyle f(n)=1/x^{\log {(n^{k})}}}$para ${\displaystyle k\geq 1}$
• ${\displaystyle f(n)=1/x^{({\log {n})}^{k}}}$para ${\displaystyle k\geq 1}$
• ${\displaystyle f(n)=1/x^{\sqrt {n}}}$

No despreciable:

• ${\displaystyle f(n)={\frac {1}{n^{\frac {1}{n}}}}}$
• ${\displaystyle f(n)={\frac {1}{x^{n(\log {n})}}}}$

Véase también

• Conjunto despreciable
• Álgebra de Colombeau
• Números no estándar
• Teorema de Gromov sobre grupos de crecimiento polinomial
• Cálculo no estándar

Referencias

1. Katz, Johnathan (6 de noviembre de 2014). Introducción a la criptografía moderna . Lindell, Yehuda (Segunda edición). Boca Raton. ISBN 9781466570269.OCLC 893721520  .{{cite book}}: Mantenimiento de CS1: falta la ubicación del editor ( enlace )

• Goldreich, Oded (2001). Fundamentos de criptografía: volumen 1, herramientas básicas. Cambridge University Press. ISBN 0-521-79172-3.
• Sipser, Michael (1997). "Sección 10.6.3: Funciones unidireccionales" . Introducción a la teoría de la computación . PWS Publishing. pp. 374–376. ISBN 0-534-94728-X.
• Papadimitriou, Christos (1993). "Sección 12.1: Funciones unidireccionales". Computational Complexity (1.ª ed.). Addison Wesley. pp. 279–298. ISBN 0-201-53082-1.
• Colombeau, Jean François (1984). Nuevas funciones generalizadas y multiplicación de distribuciones . Estudios de Matemáticas 84, Holanda Septentrional. ISBN 0-444-86830-5.
• Bellare, Mihir (1997). "Una nota sobre funciones despreciables". Journal of Cryptology . 15 . Departamento de Ciencias Informáticas e Ingeniería Universidad de California en San Diego: 2002. CiteSeerX  10.1.1.43.7900 .