En matemáticas, una función insignificante es una función tal que para cada entero positivo c existe un entero N c tal que para todo x > N c ,
De manera equivalente, también podemos usar la siguiente definición. Una funciónes despreciable , si para cada polinomio positivo poli (·) existe un entero N poli > 0 tal que para todo x > N poli
Historia
El concepto de insignificancia puede encontrar su origen en modelos sólidos de análisis. 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 como sigue (con todos los números en el dominio de números reales):
- ( Función continua ) Una función es continuo en si por cada , existe un número positivo tal que implica
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 ":
- ( Infinitesimal ) Una función continua es infinitesimal (como va al infinito) si por cada existe tal que para todos
- [ cita requerida ]
A continuación, reemplazamos por las funciones dónde o por dónde 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 puede expresar como con un polinomio constante, esto muestra que las funciones despreciables son un subconjunto de las funciones infinitesimales.
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í viene la definición en la parte superior de la página porque la longitud de la clave debe ser un número natural.
Sin embargo, la noción general de insignificancia no requiere que el parámetro de entrada es la longitud de la clave . En efecto, puede ser cualquier métrica del sistema predeterminada y el análisis matemático correspondiente ilustraría algunos comportamientos analíticos ocultos del sistema.
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 lo hacen manejable en el entorno asintótico (ver #Propiedades de cierre ). Por ejemplo, si un ataque logra 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-128 .
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. [1] Específicamente,
- Si son insignificantes, entonces la función es despreciable.
- Si es insignificante y es cualquier polinomio real, entonces la función es despreciable.
Por el contrario , si no es despreciable, entonces tampoco lo es para cualquier polinomio real .
Ejemplos de
- es insignificante para cualquier .
- es despreciable.
- es despreciable.
- es despreciable.
- no es despreciable, por positivo .
Ver también
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 . Cite journal requiere
|journal=
( ayuda )