In der Mathematik ist ein vernachlässigbarer Funktion eine Funktion, so dass für jede positive ganze Zahl, c eine ganze Zahl existiert Nc so dass für alle x & gt; Nc,

In äquivalenter Weise können wir auch die folgende Definition. Eine Funktion ist vernachlässigbar, wenn für jede positive Polynom Poly gibt es eine ganze Zahl Npoly & gt; 0, so dass für alle x & gt; Npoly

Geschichte

Das Konzept der Geringfügigkeit kann seine Spur zurück zu finden, um Modelle der Analyse klingen. Obwohl die Begriffe "Kontinuität" und "unendlich klein" wurde wichtig in der Mathematik in Newton und Leibniz Zeit, sie nicht bis in die späten 1810er gut definiert. Die erste einigermaßen strengen Definition der Kontinuität in der mathematischen Analyse war auf Bernard Bolzano, der im Jahre 1817 die moderne Definition der Stetigkeit schrieb. In letzter Zeit Cauchy, Weierstraß und Heine auch wie folgt definiert:

Dieses klassische Definition der Stetigkeit in die Definition der Geringfügigkeit in wenigen Schritten durch Ändern von Parametern in der Definition verwendet, umgewandelt werden. Zuerst wird in dem Fall, müssen wir das Konzept der "unendlich kleine Funktion" zu definieren:

Als nächstes ersetzen wir durch die Funktionen, wo oder, wo eine positive Polynom. Dies führt zu der Definition von vernachlässigbar Funktionen an der Spitze dieses Artikels angegeben. Da die Konstanten können wie bei einer konstanten Polynoms ausgedrückt zeigt dies, dass vernachlässigbare Funktionen sind eine Teilmenge der infinitesimalen Funktionen.

Verwenden Sie in Cryptography

In Komplexität basierten modernen Kryptographie, ist ein Sicherheitsschema beweisbar sichere, wenn die Wahrscheinlichkeit von Sicherheitsversagen ist vernachlässigbar in Bezug auf die Eingangs = kryptographische Schlüssellänge. Daher kommt die Definition am Anfang der Seite, weil Schlüssellänge muss eine natürliche Zahl sein.

Dennoch hat die allgemeine Vorstellung von negligibility nie gesagt, dass das System Eingabeparameter muss die Schlüssellänge ist. In der Tat kann jeder vorbestimmte System metrisch sein und entsprechende mathematische Analyse würde einige versteckte analytischen Verhalten des Systems zu veranschaulichen.

Der Kehr-of-Polynom-Formulierung wird aus dem gleichen Grund, dass Rechenbeschränktheit wird als Polynom Laufzeit definiert verwendet: es hat mathematische Verschluss Eigenschaften, die es gefügig im asymptotischen Einstellung. Zum Beispiel, wenn ein Angriff gelingt Verletzung eines Sicherheitszustand nur mit einer vernachlässigbaren Wahrscheinlichkeit und der Angriff wird ein Polynom Anzahl von Malen wiederholt, die Erfolgswahrscheinlichkeit des Gesamtangriffs bleibt vernachlässigbar. In der Praxis will man könnte, um konkretere Funktionen begrenzenden Erfolgswahrscheinlichkeit des Gegners zu haben und die Sicherheitsparameter groß genug, dass diese Wahrscheinlichkeit kleiner als ein gewisser Schwellenwert ist zu wählen, sagen 2.