Оглавление
L-обозначение
-
Определение L-нотации
- L-нотация используется для описания асимптотической скорости роста функций, связанных с вычислительной сложностью алгоритмов.
- Она включает в себя константу c и переменную α, которая может принимать значения от 0 до 1.
-
Применение в вычислительной теории чисел
- L-нотация упрощает анализ алгоритмов в вычислительной теории чисел, таких как алгоритмы разложения на множители и решения дискретных логарифмов.
-
Примеры алгоритмов с L-нотацией
- Алгоритмы целочисленной факторизации имеют субэкспоненциальную временную сложность.
- Алгоритм маленьких гигантских шагов для дискретного логарифмирования по эллиптической кривой имеет время выполнения, пропорциональное квадратному корню из размера группы.
- Тест на первичность AKS выполняется за полиномиальное время.
-
История L-нотации
- L-нотация была впервые использована Карлом Померансом с α = 1/2.
- Арьен и Хендрик Ленстры ввели формулу с двумя параметрами для анализа алгоритма дискретного логарифмирования Копперсмита.
- В настоящее время наиболее распространенной является форма с двумя параметрами.
-
Руководство по прикладной криптографии
- В руководстве по прикладной криптографии L-нотация определяется с большим O вокруг формулы, что не является стандартным определением.
- Для алгоритмов целочисленного разложения на множители и дискретного логарифмирования время выполнения не является верхней границей, поэтому определение с большим O не рекомендуется.
Полный текст статьи: