# Função desprezível

Em matemática, uma função desprezível é uma função $\mu :\mathbb {N} \to \mathbb {R}$ de modo que para cada inteiro positivo c existe um inteiro N$_c$ tal que para todo x > N$_c$,
    $|\mu (x)|<{\frac {1}{x^{c}}}.$
Da mesma forma, também podemos usar a seguinte definição: uma função $\mu :\mathbb {N} \to \mathbb {R}$ é desprezível , se para cada polinômio positivo poly(·) existe um número inteiro N$_{poly}$ > 0 tal que para todo x > N$_{poly}$
    $|\mu (x)|<{\frac {1}{\operatorname {poly} (x)}}.$

## História

O conceito de desprezibilidade pode encontrar sua origem em modelos sólidos de análise. Embora os conceitos de "continuidade" e " infinitesimal" tenham se tornado importantes na matemática durante a época de Newton e Leibniz (1680), eles não estavam bem definidos até o final da década de 1810. A primeira definição razoavelmente rigorosa de continuidade na análise matemática deveu-se a Bernard Bolzano, que escreveu em 1817 a definição moderna de continuidade. Posteriormente, Cauchy, Weierstrass e Heine também definiram da seguinte forma (com todos os números no domínio dos números reais $\mathbb {R}$):
    ( Função contínua ) Uma função $f:\mathbb {R} {\rightarrow }\mathbb {R}$ é contínua em $x=x_{0}$ se para cada $\varepsilon >0$, existe um número positivo $\delta >0$ de tal modo que $|x-x_{0}|<\delta$ implica $|f(x)-f(x_{0})|<\varepsilon .$
Esta definição clássica de continuidade pode ser transformada na definição de desprezibilidade em algumas etapas, alterando os parâmetros usados ​​na definição. Primeiro, no caso $x_{0}=\infty$ com $f(x_{0})=0$, devemos definir o conceito de "função infinitesimal":
    ( Infinitesimal ) Uma função contínua $\mu :\mathbb {R} \to \mathbb {R}$ é infinitesimal (como $x$ vai para o infinito) se para cada $\varepsilon >0$ existe $N_{\varepsilon }$ tal que para todos $x>N_{\varepsilon }$
       $|\mu (x)|<\varepsilon \,.$
Em seguida, substituímos $\varepsilon >0$ pelas funções $1/x^{c}$ onde $c>0$ ou pela $1/\operatorname {poly} (x)$ onde $\operatorname {poly} (x)$ é um polinômio positivo. Isso leva às definições de funções desprezíveis fornecidas no início deste artigo. Desde que as constantes $\varepsilon >0$ possam ser expressas como $1/\operatorname {poly} (x)$ com um polinômio constante, isso mostra que as funções desprezíveis são um subconjunto das funções infinitesimais.

## Uso em criptografia

Na criptografia moderna baseada em complexidade , um esquema de segurança é comprovadamente seguro se a probabilidade de falha de segurança (por exemplo, inverter uma função unilateral, distinguir bits pseudoaleatórios criptograficamente fortes de bits verdadeiramente aleatórios) é desprezível em termos da entrada $x$ = comprimento da chave criptográfica $n$. Daí vem a definição no topo da página porque o comprimento da chave $n$ deve ser um número natural.
No entanto, a noção geral de desprezibilidade não exige que o parâmetro de entrada $x$ seja o comprimento da chave $n$. De fato, $x$ pode ser qualquer sistema métrico predeterminado e a análise matemática correspondente ilustraria alguns comportamentos analíticos ocultos do sistema.
A formulação recíproca de polinomial é usada pela mesma razão que a delimitação computacional é definida como tempo de execução polinomial: ela tem propriedades de fechamento matemáticas que a tornam tratável no ambiente assintótico (consulte propriedades de fechamento). Por exemplo, se um ataque conseguir violar uma condição de segurança apenas com probabilidade desprezível e o ataque for repetido um número polinomial de vezes, a probabilidade de sucesso do ataque geral ainda permanece insignificante.
Na prática, pode se querer ter funções mais concretas limitando a probabilidade de sucesso do adversário e escolher o parâmetro de segurança grande o suficiente para que essa probabilidade seja menor do que algum limite, digamos 2$^{−128}$.

## Propriedades de fechamento

Uma das razões pelas quais funções desprezíveis são usadas nos fundamentos da criptografia de complexidade teórica é que elas obedecem propriedades de fechamento. Especificamente,
* Se $f,g:\mathbb {N} \to \mathbb {R}$ são desprezíveis, então a função $x\mapsto f(x)+g(x)$ é desprezível.
* Se $f:\mathbb {N} \to \mathbb {R}$ é desprezível e $p$ é qualquer polinômio real, então a função $x\mapsto p(x)\cdot f(x)$ é desprezível.
Por outro lado, se $f:\mathbb {N} \to \mathbb {R}$ não é desprezível, então também não o é $x\mapsto f(x)/p(x)$ para qualquer polinômio real $p$.

## Exemplos

* $n\mapsto x^{-n}$ é desprezível para qualquer $x\geq 2$.
* $f(n)=3^{-{\sqrt {n}}}$ é desprezível.
* $f(n)=n^{-\log n}$ é desprezível.
* $f(n)=(\log n)^{-\log n}$ é desprezível.
* $f(n)=2^{-c\log n}$ não é desprezível, para $c$ positivo.