Односторонняя функция: различия между версиями
| [отпатрулированная версия] | [отпатрулированная версия] |
Содержимое удалено Содержимое добавлено
вики на английском рядом |
|||
Строка 53:
=== Умножение и факторизация ===
Функция <math>f</math> принимает на вход два простых числа <math>p</math> и <math>q</math> в двоичном представлении и возвращает их произведение <math>N = f(p, q)</math>. Эта функция может быть вычислена за время порядка [[«O» большое и «o» малое|<math>O</math>]]<math>(n^2)</math>, где <math>n</math> — общая длина (количество двоичных чисел) входных данных. Построение обратной функции требует нахождения множителей заданного целого числа <math>N</math>. Определение множителей является очень трудоёмкой вычислительной операцией. Для оценки сложности алгоритма, раскладывающего целое число <math>N</math> на простые множители, часто используют функцию:
:: <math>L_N(\alpha, \beta) = \exp((\beta + o(1)(\ln N)^\alpha(\ln \ln N)^{1 - \alpha}))</math>
Если алгоритм имеет сложность <math>O(L_N(0, \beta))</math>, то ему требуется полиномиальное время на работу (размер задачи на входе, число бит числа, <math>\ln N</math>). При сложности <math>O(L_N(1, \beta))</math> ему потребуется уже экспоненциальное время. Таким образом скорость роста функции <math>L_N(\alpha, \beta)</math> при <math>0 < \alpha < 1</math> лежит между полиномиальной и экспоненциальной. Поэтому про алгоритмы с такой сложностью говорят, что они требуют суб-экспоненциального времени{{sfn|Смарт|2005|с = 185-186}}.
| |||