Försumbar funktion

I matematik är en försumbar funktion en funktion $\mu :\mathbb {N} \to \mathbb {R}$ så att det för varje positivt heltal c finns ett heltal N _c så att för alla x > N _c ,

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

På motsvarande sätt kan vi också använda följande definition. En funktion $\mu :\mathbb {N} \to \mathbb {R}$ är försumbar , om det för varje positivt polynom poly(·) finns ett heltal N _poly > 0 så att för alla x > N _poly

$|\mu (x)|<{\frac {1}{\operatörsnamn {poly} (x)}}.$

Historia

Begreppet negligibilitet kan hitta sitt spår tillbaka till sunda analysmodeller. Även om begreppen " kontinuitet " och " infinitesimal " blev viktiga i matematiken under Newtons och Leibniz tid (1680-talet), var de inte väldefinierade förrän i slutet av 1810-talet. Den första någorlunda rigorösa definitionen av kontinuitet i matematisk analys berodde på Bernard Bolzano , som skrev 1817 den moderna definitionen av kontinuitet. Senare Cauchy , Weierstrass och Heine också enligt följande (med alla tal i den reella taldomänen ${\displaystyle \mathbb {R} } )$ :

( Kontinuerlig funktion ) En funktion $f:\mathbb {R} {\rightarrow }\mathbb {R}$ är kontinuerlig vid $x=x_{0}$ om för varje $\varepsilon >0$ , det finns ett positivt tal $\delta >0$ så att $|x-x_{0}|<\delta$ innebär $|f(x)-f(x_{0})|<\varepsilon .$

Denna klassiska definition av kontinuitet kan omvandlas till definitionen av försumbarhet i några få steg genom att ändra parametrar som används i definitionen. Först, i fallet $x_{0}=\infty$ med $f(x_{0})=0$ , måste vi definiera begreppet " infinitesimal funktion ":

( Infinitesimal ) En kontinuerlig funktion $\mu :\mathbb {R} \to \mathbb {R}$ är infinitesimal (eftersom $x$ går till oändlighet) om för varje ${ \displaystyle \varepsilon >0}$ det finns $N_{\varepsilon }$ så att för alla $x>N_{\varepsilon }$

$|\mu (x)|<\varepsilon \,.$

Därefter ersätter vi $\varepsilon >0$ med funktionerna $1/x^{c}$ där $\displaystyle c>0}$ eller med $1/\operatornamn {poly} (x)$ där $\operatorname {poly} (x)$ är ett positivt polynom. Detta leder till definitionerna av försumbara funktioner som ges överst i den här artikeln. Eftersom konstanterna $\varepsilon >0$ kan uttryckas som $1/\operatörsnamn {poly} (x)$ med ett konstant polynom visar detta att försumbara funktioner är en delmängd av de infinitesimala funktionerna.

Använd i kryptografi

I komplexitetsbaserad modern kryptografi är ett säkerhetsschema bevisligen säkert om sannolikheten för säkerhetsfel (t.ex. invertering av en envägsfunktion , särskiljning av kryptografiskt starka pseudoslumpade bitar från verkligt slumpmässiga bitar) är försumbar när det gäller ingången $x$ = kryptografisk nyckellängd $n$ . Därav kommer definitionen överst på sidan eftersom nyckellängden $n$ måste vara ett naturligt tal.

Det allmänna begreppet försumbarhet kräver dock inte att indataparametern $x$ är nyckellängden $n$ . Faktum är att $x$ kan vara vilket förutbestämt systemmått som helst och motsvarande matematisk analys skulle illustrera några dolda analytiska beteenden hos systemet.

Formuleringen reciprocal-of-polynomial används av samma anledning som beräkningsmässig begränsning definieras som polynomisk körtid: den har matematiska stängningsegenskaper som gör den hanteringsbar i den asymptotiska miljön (se #Stängningsegenskaper ). Till exempel, om en attack lyckas bryta ett säkerhetsvillkor endast med försumbar sannolikhet, och attacken upprepas ett polynomantal gånger, förblir sannolikheten för framgång för den övergripande attacken fortfarande försumbar.

I praktiken kanske man vill ha mer konkreta funktioner som begränsar motståndarens framgångssannolikhet och välja säkerhetsparametern som är tillräckligt stor för att denna sannolikhet är mindre än någon tröskel, säg 2 ⁻¹²⁸ .

Stängningsegenskaper

En av anledningarna till att försumbara funktioner används i grunderna för komplexitetsteoretisk kryptografi är att de följer stängningsegenskaper. Specifikt,

1. Om $f,g:\mathbb {N} \to \mathbb {R}$ är försumbara, då är funktionen $x\ mapsto f(x)+g(x)$ är försumbar.
2. Om $f:\mathbb {N} \to \mathbb {R}$ är försumbar och $p$ är vilket reellt polynom som helst, då är funktionen $x\mapsto p(x)\cdot f(x)$ är försumbar.

Omvänt , om $f:\mathbb {N} \to \mathbb {R}$ inte är försumbar, så är inte heller $x\mapsto f(x)/p(x)$ för valfritt reellt polynom $p$ .

Exempel

• $n\mapsto a^{-n}$ är försumbar för alla $a\geq 2$ .
• $f(n)=3^{-{\sqrt {n}}}$ är försumbar.
• $f(n)=n^{-\log n}$ är försumbar.
• $f(n)=(\log n)^{-\log n}$ är försumbar.
• $f(n)=2^{-c\log n}$ är inte försumbar, för positivt $c$ .

Givet: n > 0 och gräns som n-> oändlighet:

Försumbar :

• $f(n)=1/x^{n/2}eller1/x^{(}log(n^{2})eller1/x^{l}og( n)or1/x^{(}logga)^{2}eller1/x^{s}qrt(n)$

Icke försumbar:

• $f(n)=1/n^{(}1/n)or1/ x^{(}n*(log(n))$

Se även

• Försumbar set
• Colombeau algebra
• Ostandardiserade siffror
• Gromovs teorem om grupper av polynomtillväxt
• Icke-standard kalkyl

•   Goldreich, Oded (2001). Kryptografins grunder: Volym 1, grundläggande verktyg . Cambridge University Press. ISBN 0-521-79172-3 .
•   Sipser, Michael (1997). "Avsnitt 10.6.3: Envägsfunktioner" . Introduktion till teorin om beräkning . PWS Publishing. s. 374–376 . ISBN 0-534-94728-X .
•   Papadimitriou, Christos (1993). "Avsnitt 12.1: Envägsfunktioner". Computational Complexity (1:a upplagan). Addison Wesley. s. 279 -298. ISBN 0-201-53082-1 ​​.
•   Colombeau, Jean François (1984). Nya generaliserade funktioner och multiplikation av distributioner . Mathematics Studies 84, North Holland. ISBN 0-444-86830-5 .
•   Bellare, Mihir (1997). "En anmärkning om försumbara funktioner". Journal of Cryptology . Institutionen för datavetenskap och teknik University of California i San Diego. 15 : 2002. CiteSeerX 10.1.1.43.7900 .