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

В математике пренебрежимо малая функция — это функция , такая что для каждого положительного целого числа 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 |x-x_{0}|<\delta }$ ${\displaystyle |f(x)-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 }}$ ${\displaystyle x>N_{\varepsilon }}$

${\displaystyle |\mu (x)|<\varepsilon \,.}$^{[ необходима ссылка ]}

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

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

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

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

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

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

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

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

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

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

Примеры

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

Предположим , мы берем предел как : ${\displaystyle n>0}$ ${\displaystyle n\to \infty }$

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

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

Немаловажное:

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

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

• Незначительный набор
• алгебра Коломбо
• Нестандартные числа
• Теорема Громова о группах полиномиального роста
• Нестандартное исчисление

Ссылки

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

• Goldreich, Oded (2001). Основы криптографии: Том 1, Основные инструменты. Cambridge University Press. ISBN 0-521-79172-3.
• Sipser, Michael (1997). "Раздел 10.6.3: Односторонние функции" . Введение в теорию вычислений . PWS Publishing. стр. 374–376. ISBN 0-534-94728-X.
• Пападимитриу, Христос (1993). "Раздел 12.1: Односторонние функции". Computational Complexity (1-е изд.). Addison Wesley. стр. 279–298. ISBN 0-201-53082-1.
• Коломбо, Жан Франсуа (1984). Новые обобщенные функции и умножение распределений . Mathematics Studies 84, Северная Голландия. ISBN 0-444-86830-5.
• Белларе, Михир (1997). «Замечание о пренебрежимо малых функциях». Журнал криптологии . 15 . Кафедра компьютерных наук и инженерии Калифорнийского университета в Сан-Диего: 2002. CiteSeerX  10.1.1.43.7900 .