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

В математике пренебрежимо малой функцией называется функция $\mu :\mathbb {N} \to \mathbb {R}$ такой, что для каждого натурального числа c существует целое число N _c такое, что для всех x > N _c ,

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

Эквивалентно мы можем также использовать следующее определение.Функция $\mu :\mathbb {N} \to \mathbb {R}$ пренебрежимо мал , если для каждого положительного многочлена поли(·) существует целое число N _поли > 0 такое, что для всех x > N _поли

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

История

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

( Непрерывная функция ) Функция

f:\mathbb {R} {\rightarrow }\mathbb {R}

является непрерывным в

x=x_{0}

если для каждого

\varepsilon >0

, существует положительное число

\delta >0

такой, что

|x-x_{0}|<\delta

подразумевает

|f(x)-f(x_{0})|<\varepsilon .

Это классическое определение непрерывности можно трансформировать вопределение ничтожности за несколько шагов путем изменения параметров, используемых в определении. Во-первых, в случае $x_{0}=\infty$ с $f(x_{0})=0$ , нам необходимо определить понятие « бесконечно малой функции »:

( Бесконечно малая ) Непрерывная функция

\mu :\mathbb {R} \to \mathbb {R}

( бесконечно мала так как

x

стремится к бесконечности), если для каждого

\varepsilon >0

существует

N_{\varepsilon }

такой, что для всех

x>N_{\varepsilon }

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

^{[ нужна ссылка ]}

Далее заменим $\varepsilon >0$ по функциям $1/x^{c}$ где $c>0$ или через $1/\operatorname {poly} (x)$ где $\operatorname {poly} (x)$ является положительным полиномом . Это приводит к определениям пренебрежимо малых функций, данным в начале этой статьи. Поскольку константы $\varepsilon >0$ может быть выражено как $1/\operatorname {poly} (x)$ с постоянным полиномом это показывает, что бесконечно малые функции являются надмножеством незначительных функций.

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

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

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

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

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

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

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

Если $f,g:\mathbb {N} \to \mathbb {R}$ пренебрежимо малы, то функция $x\mapsto f(x)+g(x)$ ничтожно мало.
Если $f:\mathbb {N} \to \mathbb {R}$ является ничтожным и $p$ — любой действительный полином, то функция $x\mapsto p(x)\cdot f(x)$ ничтожно мало.

И наоборот , если $f:\mathbb {N} \to \mathbb {R}$ не является незначительным, то и не является $x\mapsto f(x)/p(x)$ для любого действительного многочлена $p$ .

Примеры

$n\mapsto a^{-n}$ ничтожно мало для любого $a\geq 2$ .
$f(n)=3^{-{\sqrt {n}}}$ ничтожно мало.
$f(n)=n^{-\log n}$ ничтожно мало.
$f(n)=(\log n)^{-\log n}$ ничтожно мало.
$f(n)=2^{-c\log n}$ не является незначительным, для положительного $c$ .

Предполагать $n>0$ , мы принимаем предел как $n\to \infty$ :

Незначительно :

$f(n)=1/x^{n/2}$
$f(n)=1/x^{\log {(n^{k})}}$ для $k\geq 1$
$f(n)=1/x^{({\log {n})}^{k}}$ для $k\geq 1$
$f(n)=1/x^{\sqrt {n}}$

Незначительный:

$f(n)={\frac {1}{n^{\frac {1}{n}}}}$
$f(n)={\frac {1}{x^{n(\log {n})}}}$

См. также

Ссылки

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

Гольдрейх, Одед (2001). Основы криптографии: Том 1, Основные инструменты . Издательство Кембриджского университета. ISBN 0-521-79172-3 .
Сипсер, Майкл (1997). «Раздел 10.6.3: Односторонние функции» . Введение в теорию вычислений . Издательство ПВС. стр. 374–376 . ISBN 0-534-94728-Х .
Пападимитриу, Христос (1993). «Раздел 12.1: Односторонние функции». Вычислительная сложность (1-е изд.). Эддисон Уэсли. стр. 279–298 . ISBN 0-201-53082-1 .
Коломбо, Жан Франсуа (1984). Новые обобщенные функции и умножение распределений . Математические исследования 84, Северная Голландия. ISBN 0-444-86830-5 .
Белларе, Михир (1997). «Замечание о пренебрежимо малых функциях». Журнал криптологии . 15 . Кафедра компьютерных наук и инженерии Калифорнийского университета в Сан-Диего: 2002. CiteSeerX 10.1.1.43.7900 .

[1] Кац, Джонатан (6 ноября 2014 г.). Введение в современную криптографию . Линделл, Иегуда (второе изд.). Бока Ратон. ISBN 9781466570269 . OCLC 893721520 . {{cite book}}: CS1 maint: отсутствует местоположение издателя ( ссылка )

[1]