Función insignificante - Negligible function

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 por cada polinomio positivo poli (·) existe un 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 de análisis sólidos. Aunque los conceptos de " continuidad " e " infinitesimal " se volvieron importantes 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 con , debemos definir el concepto de " función infinitesimal ": ${\ Displaystyle x_ {0} = \ infty}$${\ Displaystyle f (x_ {0}) = 0}$

( Infinitesimal ) Una función continua es infinitesimal (como va 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 \ ,.}$

A continuación, reemplazamos por las funciones where o by where es un polinomio positivo. Esto conduce 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 despreciables son un subconjunto de las funciones infinitesimales. ${\ Displaystyle \ varepsilon> 0}$${\ Displaystyle 1 / x ^ {c}}$${\ Displaystyle c> 0}$${\ Displaystyle 1 / \ operatorname {poli} (x)}$${\ Displaystyle \ operatorname {poli} (x)}$${\ Displaystyle \ varepsilon> 0}$${\ Displaystyle 1 / \ operatorname {poli} (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 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 ser cualquier sistema métrico predeterminado 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 por la que la delimitación computacional se define como tiempo de ejecución polinomial: tiene propiedades matemáticas de cierre que la hacen manejable en el entorno asintótico (ver #Propiedades de cierre ). Por ejemplo, si un ataque tiene éxito en violar una condición de seguridad solo con una probabilidad insignificante, y el ataque se repite un número polinomial 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 teórica de la complejidad es que obedecen a propiedades de cierre. Específicamente,

1. Si son insignificantes, entonces la función es insignificante.${\ 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 x ^ {- n}}$es insignificante para cualquiera .${\ Displaystyle x \ 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}$

Ver también

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

Referencias

• 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 de 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. 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 insignificantes". Departamento de Ciencias de la Computación e Ingeniería de la Universidad de California en San Diego. CiteSeerX  10.1.1.43.7900 . Citar diario requiere |journal=( ayuda )