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}$

 Paso : Esta es una función de decaimiento exponencial donde es una constante mayor o igual a 2. Como , muy rápidamente, lo que lo hace insignificante. ${\displaystyle a}$ ${\displaystyle n\to \infty }$ ${\displaystyle a^{-n}\to 0}$

• ${\displaystyle f(n)=3^{-{\sqrt {n}}}}$es insignificante:

 Paso : Esta función tiene un decaimiento exponencial con una base de 3, pero el exponente crece más lentamente que (solo en ). Como , , por lo que sigue siendo insignificante, pero decae más lentamente que . ${\displaystyle n}$ ${\displaystyle {\sqrt {n}}}$ ${\displaystyle n\to \infty }$ ${\displaystyle 3^{-{\sqrt {n}}}\to 0}$ ${\displaystyle 3^{-n}}$

• ${\displaystyle f(n)=n^{-\log n}}$es insignificante:

 Paso : En este caso, representa una desintegración polinómica, con un exponente que crece negativamente debido a . Dado que la tasa de desintegración aumenta con , la función tiende a 0 más rápido que las funciones polinómicas como para cualquier constante , lo que la hace despreciable. ${\displaystyle n^{-\log n}}$ ${\displaystyle \log n}$ ${\displaystyle n}$ ${\displaystyle n^{-k}}$ ${\displaystyle k}$

• ${\displaystyle f(n)=(\log n)^{-\log n}}$es insignificante:

 Paso : Esta función decae como el logaritmo de elevado a un exponente negativo , lo que conduce a una aproximación rápida a 0 como . La decaimiento aquí es más rápida que las tasas logarítmicas inversas o polinómicas, lo que la hace insignificante. ${\displaystyle n}$ ${\displaystyle -\log n}$ ${\displaystyle n\to \infty }$

• ${\displaystyle f(n)=2^{-c\log n}}$No es despreciable, por positivo : ${\displaystyle c}$

 Paso : Podemos reescribir esto como , que es una desintegración polinómica en lugar de exponencial. Como es positiva, como , pero no decae tan rápido como las funciones exponenciales verdaderas con respecto a , lo que la hace no despreciable. ${\displaystyle f(n)=n^{-c}}$ ${\displaystyle c}$ ${\displaystyle f(n)\to 0}$ ${\displaystyle n\to \infty }$ ${\displaystyle n}$

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

Despreciable:

• ${\displaystyle f(n)={\frac {1}{x^{n/2}}}}$:

 Paso : Esta función decae exponencialmente con la base elevada a la potencia de . Como , rápidamente, lo que la hace despreciable. ${\displaystyle x}$ ${\displaystyle -{\frac {n}{2}}}$ ${\displaystyle n\to \infty }$ ${\displaystyle x^{-{\frac {n}{2}}}\to 0}$

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

 Paso : Podemos simplificar como , que decae más rápido que cualquier polinomio. Como , la función se acerca a cero y se considera despreciable para cualquier y . ${\displaystyle x^{-\log(n^{k})}}$ ${\displaystyle n^{-k\log x}}$ ${\displaystyle n\to \infty }$ ${\displaystyle k\geq 1}$ ${\displaystyle x>1}$

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

 Paso : La desintegración está determinada por la base elevada a la potencia de . Como crece con , esta función se acerca a cero más rápido que la desintegración polinómica, lo que la hace despreciable. ${\displaystyle x}$ ${\displaystyle -(\log n)^{k}}$ ${\displaystyle (\log n)^{k}}$ ${\displaystyle n}$

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

 Paso : Aquí, decae exponencialmente con una base de elevada a . Como , rápidamente, por lo que se considera insignificante. ${\displaystyle f(n)}$ ${\displaystyle x}$ ${\displaystyle -{\sqrt {n}}}$ ${\displaystyle n\to \infty }$ ${\displaystyle f(n)\to 0}$

No despreciable:

• ${\displaystyle f(n)={\frac {1}{n^{1/n}}}}$:

 Paso : Dado que , esta función decae muy lentamente y no logra aproximarse a cero lo suficientemente rápido como para ser considerada insignificante. ${\displaystyle n^{1/n}\to 1}$ ${\displaystyle n\to \infty }$

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

 Paso : Con una base y un exponente exponenciales , esta función se acercaría a cero muy rápidamente, lo que sugiere que es insignificante. ${\displaystyle 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}}: CS1 maint: location missing publisher (link)

• 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.
• Bellaré, Mihir (1997). "Una nota sobre funciones insignificantes". Revista de criptología . 15 . Departamento de Ingeniería y Ciencias de la Computación Universidad de California en San Diego: 2002. CiteSeerX  10.1.1.43.7900 .