Zanedbatelná funkce - Negligible function

V matematice, a zanedbatelná funkce je funkce ${displaystyle mu: mathbb {N} o mathbb {R}}$ tak, že pro každé kladné celé číslo C existuje celé číslo N_C takové, že pro všechny X > N_C,

{displaystyle | mu (x) | <{frac {1} {x ^ {c}}}.}

Rovněž můžeme použít následující definici. Funkce ${displaystyle mu: mathbb {N} o mathbb {R}}$ je zanedbatelný, pokud pro každého pozitivní polynom poly (·) existuje celé číslo N_poly > 0 takové, že pro všechny X > N_poly

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

Dějiny

Koncept zanedbatelnost může najít jeho stopu zpět ke zvukovým modelům analýzy. Ačkoli pojmy „kontinuita " a "infinitezimální "se stal důležitým v matematice během Newton a Leibniz (1680), nebyly přesně definovány až do konce 10. První přiměřeně přísná definice kontinuita v matematická analýza bylo kvůli Bernard Bolzano, který napsal v roce 1817 moderní definici kontinuity. Později Cauchy, Weierstrass a Heine také definováno následovně (se všemi čísly v doméně reálných čísel ${displaystyle mathbb {R}}$ ):

(Kontinuální funkce ) Funkce

{displaystyle f: mathbb {R} {ightarrow} mathbb {R}}

je kontinuální na

{displaystyle x = x_ {0}}

pokud pro každého

{displaystyle varepsilon> 0}

, existuje kladné číslo

{displaystyle delta> 0}

takhle

{displaystyle | x-x_ {0} |

naznačuje

{displaystyle | f (x) -f (x_ {0}) |

Tuto klasickou definici kontinuity lze v několika krocích převést na definici zanedbatelnosti změnou parametrů použitých v definici. Nejprve v případě ${displaystyle x_ {0} = infty}$ s ${displaystyle f (x_ {0}) = 0}$ , musíme definovat pojem „nekonečně malá funkce":

(Infinitezimální ) Kontinuální funkce

{displaystyle mu: mathbb {R} o mathbb {R}}

je infinitezimální (tak jako

{displaystyle x}

jde do nekonečna) pokud pro každého

{displaystyle varepsilon> 0}

tady existuje

{displaystyle N_ {varepsilon}}

takové, že pro všechny

{displaystyle x> N_ {varepsilon}}

{displaystyle | mu (x) |

^{[Citace je zapotřebí ]}

Dále vyměníme ${displaystyle varepsilon> 0}$ podle funkcí ${displaystyle 1 / x ^ {c}}$ kde ${displaystyle c> 0}$ nebo ${displaystyle 1 / operatorname {poly} (x)}$ kde ${displaystyle operatorname {poly} (x)}$ je pozitivní polynom. To vede k definici zanedbatelných funkcí uvedených v horní části tohoto článku. Protože konstanty ${displaystyle varepsilon> 0}$ lze vyjádřit jako ${displaystyle 1 / operatorname {poly} (x)}$ s konstantním polynomem to ukazuje, že zanedbatelné funkce jsou podmnožinou infinitezimálních funkcí.

Použití v kryptografii

Ve složitosti založené na moderním kryptografie, bezpečnostní schéma jeprokazatelně bezpečný pokud je pravděpodobnost selhání zabezpečení (např. invertování a jednosměrná funkce, rozlišující kryptograficky silné pseudonáhodné bity ze skutečně náhodných bitů) je zanedbatelný z hlediska vstupu ${displaystyle x}$ = délka kryptografického klíče ${displaystyle n}$ . Proto přichází definice v horní části stránky, protože délka klíče ${displaystyle n}$ musí být přirozené číslo.

Obecná představa zanedbatelnosti nicméně nevyžaduje, aby byl vstupní parametr ${displaystyle x}$ je délka klíče ${displaystyle n}$ . Vskutku, ${displaystyle x}$ může být libovolná předem určená metrika systému a odpovídající matematická analýza by ilustrovala některá skrytá analytická chování systému.

Reciproční polynomiální formulace se používá ze stejného důvodu výpočetní omezenost je definován jako doba běhu polynomu: má matematické uzavírací vlastnosti, díky nimž je v souboru asymptotické nastavení (viz # Vlastnosti uzavření ). Například pokud útok úspěšně poruší bezpečnostní podmínku jen se zanedbatelnou pravděpodobností a útok se opakuje polynomiálně, pravděpodobnost úspěchu celkového útoku zůstane zanedbatelná.

V praxi by člověk mohl chtít mít více beton funkce ohraničující pravděpodobnost úspěchu protivníka a zvolit dostatečně velký bezpečnostní parametr, aby tato pravděpodobnost byla menší než nějaká prahová hodnota, řekněme 2⁻¹²⁸.

Vlastnosti uzavření

Jedním z důvodů, proč se v základech používají zanedbatelné funkce teoretická složitost kryptografie spočívá v tom, že dodržují uzavírací vlastnosti.^[1] Konkrétně

Li ${displaystyle f, g: mathbb {N} o mathbb {R}}$ jsou zanedbatelné, pak funkce ${displaystyle xmapsto f (x) + g (x)}$ je zanedbatelný.
Li ${displaystyle f: mathbb {N} o mathbb {R}}$ je zanedbatelný a ${displaystyle p}$ je jakýkoli skutečný polynom, pak funkce ${displaystyle xmapsto p (x) cdot f (x)}$ je zanedbatelný.

Naopak, pokud ${displaystyle f: mathbb {N} o mathbb {R}}$ není zanedbatelné, pak ani není ${displaystyle xmapsto f (x) / p (x)}$ pro jakýkoli skutečný polynom ${displaystyle p}$ .

Příklady

${displaystyle nmapsto x ^ {- n}}$ je pro všechny zanedbatelné ${displaystyle xgeq 2}$ .
${displaystyle f (n) = 3 ^ {- {sqrt {n}}}}$ je zanedbatelný.
${displaystyle f (n) = n ^ {- přihlásit se}}$ je zanedbatelný.
${displaystyle f (n) = (log n) ^ {- přihlásit n}}$ je zanedbatelný.
${displaystyle f (n) = 2 ^ {- ucpat n}}$ není zanedbatelné, pro pozitivní ${displaystyle c}$ .

Viz také

Reference

^ Katz, Johnathan (6. listopadu 2014). Úvod do moderní kryptografie. Lindell, Yehuda (druhé vydání). Boca Raton. ISBN 9781466570269. OCLC 893721520.

Goldreich, Oded (2001). Základy kryptografie: Svazek 1, Základní nástroje. Cambridge University Press. ISBN 0-521-79172-3.
Sipser, Michael (1997). "Část 10.6.3: Jednosměrné funkce". Úvod do teorie výpočtu. PWS Publishing. str.374–376. ISBN 0-534-94728-X.
Papadimitriou, Christos (1993). "Část 12.1: Jednosměrné funkce". Výpočetní složitost (1. vyd.). Addison Wesley. str.279 –298. ISBN 0-201-53082-1.
Colombeau, Jean François (1984). Nové zobecněné funkce a násobení distribucí. Mathematics Studies 84, North Holland. ISBN 0-444-86830-5.
Bellare, Mihir (1997). Msgstr "Poznámka k zanedbatelným funkcím". Katedra počítačové vědy a techniky University of California v San Diegu. CiteSeerX 10.1.1.43.7900. Citovat deník vyžaduje | deník = (Pomoc)

[1] Katz, Johnathan (6. listopadu 2014). Úvod do moderní kryptografie. Lindell, Yehuda (druhé vydání). Boca Raton. ISBN 9781466570269. OCLC 893721520.

[1]