Función insignificante

En matemáticas, una función insignificante es una función tal que para cada entero positivo c existe un número 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 usar la siguiente definición. Una función es despreciable , si para cada polinomio positivo poli(·) existe un número entero N _poli  > 0 tal que para todo x  >  N _poli ${\displaystyle \mu :\mathbb {N} \to \mathbb {R} }$

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

Historia

El concepto de insignificancia puede encontrar su origen en modelos sólidos de análisis. Aunque los conceptos de " continuidad " e " infinitésimo " adquirieron importancia en las matemáticas durante la época de Newton y Leibniz (década de 1680), no estuvieron bien definidos hasta finales 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. Posteriormente Cauchy , Weierstrass y Heine también definieron de la siguiente manera (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 cambiando los parámetros utilizados en la definición. Primero, 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 (que llega al infinito) si para cada existe tal que para todos ${\displaystyle \mu :\mathbb {R} \to \mathbb {R} }$ ${\displaystyle x}$ ${\displaystyle \varepsilon >0}$ ${\displaystyle N_{\varepsilon }}$ ${\displaystyle x>N_{\varepsilon }}$

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

A continuación, reemplazamos por las funciones dónde o por dónde es un polinomio positivo . Esto lleva a las definiciones de funciones insignificantes que se dan al principio de este artículo. Dado que las constantes se pueden expresar como con un polinomio constante, esto muestra que las funciones infinitesimales son un superconjunto de funciones insignificantes. ${\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 entrada = longitud de la clave criptográfica. . De ahí viene 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 haber 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 polinomio se utiliza por la misma razón que la acotación computacional se define como tiempo de ejecución polinomial: tiene propiedades de cierre matemático que lo hacen manejable en el entorno asintótico (consulte #Propiedades de cierre). Por ejemplo, si un ataque logra violar una condición de seguridad sólo con una probabilidad insignificante y el ataque se repite un número polinómico de veces, la probabilidad de éxito del ataque general sigue siendo insignificante.

En la práctica, uno podría querer tener funciones más concretas que limiten la probabilidad de éxito del adversario y elegir el parámetro de seguridad lo suficientemente grande como para que esta probabilidad sea menor que algún umbral, digamos 2 ⁻¹²⁸ .

Propiedades de cierre

Una de las razones por las que se utilizan funciones insignificantes en los fundamentos de la criptografía de 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, tampoco 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 cualquiera . ${\displaystyle a\geq 2}$
• ${\displaystyle f(n)=3^{-{\sqrt {n}}}}$es despreciable.
• ${\displaystyle f(n)=n^{-\log n}}$es despreciable.
• ${\displaystyle f(n)=(\log n)^{-\log n}}$es despreciable.
• ${\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})}}}}$

Ver también

• Conjunto insignificante
• álgebra de colombeau
• Números no estándar
• Teorema de Gromov sobre grupos de crecimiento polinómico
• Cálculo no estándar

Referencias

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

• Goldreich, Oded (2001). Fundamentos de la criptografía: Volumen 1, Herramientas básicas. Prensa de la Universidad de Cambridge. 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 . Publicación PWS. págs. 374–376. ISBN 0-534-94728-X.
• Papadimitriou, Christos (1993). "Sección 12.1: Funciones unidireccionales". Complejidad computacional (1ª ed.). Addison Wesley. págs. 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 .