WikiDer > Незначительная функция

Negligible function

В математике незначительная функция это функция такой, что для каждого положительного целого числа c существует целое число Nc такой, что для всех Икс > Nc,

Аналогично, мы также можем использовать следующее определение. является незначительный, если для каждого положительный многочлен poly (·) существует целое число Nполи > 0 такое, что для всех Икс > Nполи

История

Концепция чего-либо ничтожность можно найти его след в надежных моделях анализа. Хотя понятия "непрерывность" и "бесконечно малый"стали важными в математике во время Ньютон и Лейбницво времена (1680-е годы) они не были четко определены до конца 1810-х годов. Первое достаточно строгое определение непрерывность в математический анализ был по причине Бернар Больцано, написавший в 1817 г. современное определение преемственности. Потом Коши, Weierstrass и Гейне также определяется следующим образом (со всеми числами в области действительных чисел ):

(Непрерывная функция) Функция является непрерывный в если для каждого , существует положительное число такой, что подразумевает

Это классическое определение непрерывности может быть преобразовано в определение незначимости за несколько шагов, изменив параметры, используемые в определении. Во-первых, в случае с , мы должны определить понятие "бесконечно малая функция":

(Бесконечно малый) Непрерывная функция является бесконечно малый (в качестве стремится к бесконечности), если для каждого Существует такой, что для всех
[нужна цитата]

Далее заменяем по функциям куда или по куда - положительный многочлен. Это приводит к определениям незначительных функций, приведенным в верхней части этой статьи. Поскольку константы можно выразить как с постоянным полиномом это показывает, что незначительные функции являются подмножеством бесконечно малых функций.

Использование в криптографии

В сложных современных криптография, схема безопасностидоказуемо безопасный если вероятность отказа безопасности (например, инвертирование односторонняя функция, различая криптографически стойкие псевдослучайные биты из действительно случайных битов) незначительный с точки зрения ввода = длина криптографического ключа . Отсюда следует определение вверху страницы, потому что длина ключа должно быть натуральным числом.

Тем не менее, общее понятие незначимости не требует, чтобы входной параметр длина ключа . В самом деле, может быть любой заранее заданной системной метрикой, и соответствующий математический анализ проиллюстрирует некоторые скрытые аналитические характеристики системы.

Формулировка обратного полинома используется по той же причине, что и вычислительная ограниченность определяется как полиномиальное время работы: у него есть математические свойства закрытия, которые делают его управляемым в асимптотический установка (см. #Closure properties). Например, если при атаке удается нарушить условие безопасности только с пренебрежимо малой вероятностью, и атака повторяется полиномиальное количество раз, вероятность успеха всей атаки по-прежнему остается незначительной.

На практике может потребоваться больше конкретный функции, ограничивающие вероятность успеха злоумышленника, и выбрать параметр безопасности достаточно большим, чтобы эта вероятность была меньше некоторого порога, скажем 2−128.

Свойства закрытия

Одна из причин того, что незначительные функции используются в основах теоретико-сложный криптография заключается в том, что они подчиняются свойствам закрытия.[1] Конкретно,

  1. Если пренебрежимо малы, то функция незначительно.
  2. Если незначительно и - любой действительный многочлен, то функция незначительно.

Наоборот, если нельзя пренебречь, то и для любого действительного многочлена .

Примеры

  • ничтожно мал для любого .
  • незначительно.
  • незначительно.
  • незначительно.
  • не пренебрежимо мало, для положительного .

Смотрите также

Рекомендации

  1. ^ Кац, Джонатан (6 ноября 2014 г.). Введение в современную криптографию. Линделл, Иегуда (Второе изд.). Бока-Ратон. ISBN 9781466570269. OCLC 893721520.