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

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

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

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

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

История [ править ]

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

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

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

{\ displaystyle x = x_ {0}}

{\ displaystyle \ varepsilon> 0}

{\ displaystyle \ delta> 0}

{\ Displaystyle | х-х_ {0} | <\ delta}

{\ Displaystyle | е (х) -f (x_ {0}) | <\ varepsilon.}

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

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

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

{\ displaystyle x}

{\ displaystyle \ varepsilon> 0}

{\ Displaystyle 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$

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

На практике может потребоваться иметь более конкретные функции, ограничивающие вероятность успеха злоумышленника, и выбрать параметр безопасности достаточно большим, чтобы эта вероятность была меньше некоторого порога, скажем, 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$

Примеры [ править ]

Этот раздел нуждается в расширении . Вы можете помочь, добавив к нему . ( Март 2018 г. )

$n\mapsto x^{-n}$ ничтожно мал для любого . $x\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$

См. Также [ править ]

Ссылки [ править ]

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

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

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

[1] В