Funkcja zaniedbywalna

Funkcja zaniedbywalna – funkcja, która dąży do zera szybciej niż dowolny wielomian. Funkcje takie mają szczególne znaczenie w kryptografii. Formalnie jest zaniedbywalna, jeśli dla dowolnego istnieje takie, że zachodzi Przykładami takich funkcji są np. i Funkcje zaniedbywalne są używane do określania bezpieczeństwa algorytmów i protokołów kryptograficznych. Przykładowo możemy powiedzieć, że szyfr jest bezpieczny, jeśli szansa odgadnięcia klucza przez osobę postronną jest zaniedbywalną funkcją długości klucza. Definicja funkcji zaniedbywalnej jest asymptotyczna z identycznych powodów, dla których tak definiowane są złożoności algorytmów: w takiej postaci jest zamknięta na podstawowe matematyczne operacje, co umożliwia wyprowadzanie innych własności z tej definicji. W praktyce bezpieczeństwo systemów kryptograficznych wymaga ustalenia konkretnych wartości tej funkcji (np. 2−128) i użycia klucza o takiej długości, aby tę wartość uzyskać.