Дискретный логарифм

В математике для данных действительных чисел a и b логарифм такое , log _b   a — это число x что b ^х = а . Аналогично, в любой группе G степени b ^к может быть определен для всех целых чисел k , а дискретный логарифм log _b   a представляет собой целое число k такое, что b ^к = а . В теории чисел более часто используемый термин — индекс : мы можем написать x = ind _r a (mod m ) (читай «индекс a по основанию r по модулю m ») для r ^х ≡ a (mod m ), если r — примитивный корень из m и НОД ( a , m ) = 1.

В некоторых особых случаях дискретные логарифмы можно быстро вычислить. Однако эффективный метод их вычисления в целом неизвестен. В криптографии вычислительная сложность задачи дискретного логарифмирования вместе с ее применением была впервые предложена в задаче Диффи–Хеллмана . Некоторые важные алгоритмы в криптографии с открытым ключом , такие как Эль-Гамаль , основывают свою безопасность на предположении о том, что задача дискретного логарифмирования (DLP) над тщательно выбранными группами не имеет эффективного решения.

Определение

Пусть G — любая группа. Обозначим его групповую операцию умножением, а его единичный элемент — 1. Пусть b — любой элемент G . Для любого положительного целого числа k выражение b ^к обозначает произведение b на самого себя k раз:

$b^{k}=\underbrace {b\cdot b\cdot \ldots \cdot b} _{k\;{\text{factors}}}.$

Аналогично, пусть b ^{- к} обозначим произведение b ⁻¹ сам с собой k раз. При k = 0 k -я степень равна единице: b ⁰ = 1 .

Пусть a также является элементом G . Целое число k , которое решает уравнение b ^к = a называется дискретным логарифмом (или просто логарифмом в данном контексте) a по основанию b . Пишут k = log _b   a .

Примеры

Степени 10

Степени числа 10 равны

$\ldots ,0.001,0.01,0.1,1,10,100,1000,\ldots .$

Для любого числа a в этом списке можно вычислить log ₁₀   a . Например, log ₁₀ 10000 = 4 и log ₁₀ 0,001 = −3. Это примеры проблемы дискретного логарифма.

Другие логарифмы по основанию 10 в действительных числах не являются примерами проблемы дискретного логарифма, поскольку они включают нецелые показатели степени. Например, уравнение log ₁₀ 53 = 1,724276… означает, что 10 ^1.724276… = 53. Хотя целочисленные показатели степени могут быть определены в любой группе с использованием произведений и обратных величин, произвольные действительные показатели степени, такие как 1,724276…, требуют других понятий, таких как показательная функция .

С точки зрения теории групп , степени 10 образуют циклическую группу G при умножении, а 10 является генератором этой группы. Дискретный логарифм log ₁₀   a определен для любого a в G .

Степени фиксированного действительного числа

Аналогичный пример справедлив для любого ненулевого действительного числа b . Степени образуют мультипликативную подгруппу G = {…, b ⁻³ , б ⁻² , б ⁻¹ , 1, б ¹ , б ² , б ³ , …} ненулевых действительных чисел. Для любого элемента a из G можно вычислить log _b   a .

Модульная арифметика

Одной из простейших настроек дискретных логарифмов является группа Z _p ^× . Это группа умножения по модулю числа простого p . Его элементы представляют собой ненулевые классы конгруэнтности по модулю p , а групповое произведение двух элементов может быть получено обычным целочисленным умножением элементов с последующим сокращением по модулю p .

K - я степень одного из чисел в этой группе может быть вычислена путем нахождения его k -й степени как целого числа, а затем нахождения остатка после деления на p . Когда задействованные числа большие, эффективнее многократно уменьшать модуль p во время вычислений. Независимо от конкретного используемого алгоритма, эта операция называется модульным возведением в степень . Например, рассмотрим Z ₁₇ ^× . Чтобы вычислить 3 ⁴ в этой группе вычислите 3 ⁴ = 81, а затем разделите 81 на 17, получив в остатке 13. Таким образом, 3 ⁴ = 13 в группе Z ₁₇ ^× .

Дискретный логарифм — это просто обратная операция. Например, рассмотрим уравнение 3 ^к ≡ 13 (по модулю 17). В приведенном выше примере одно решение — k = 4, но это не единственное решение. С 3 ¹⁶ ≡ 1 (mod 17) — как следует из малой теоремы Ферма — отсюда также следует, что если n — целое число, то 3 ^{4+16 н} ≡ 3 ⁴ × (3 ¹⁶ ) ^н ≡ 13 × 1 ^н ≡ 13 (по модулю 17). Следовательно, уравнение имеет бесконечно много решений вида 4 + 16 n . Более того, поскольку 16 — это наименьшее положительное целое число m, удовлетворяющее условию 3 ^м ≡ 1 (по модулю 17), это единственные решения. Эквивалентно, множество всех возможных решений может быть выражено ограничением k ≡ 4 (mod 16).

Полномочия личности

В частном случае, когда b является единичным элементом 1 группы G , дискретный логарифм log _b   a не определен для a, отличного от 1, и каждое целое число k является дискретным логарифмом для a = 1.

Характеристики

Степени подчиняются обычному алгебраическому тождеству b ^{к + л} = б ^к  б ^л . Другими словами, функция

$f\colon \mathbf {Z} \to G$

определяется как f ( k ) = b ^к является групповым гомоморфизмом целых чисел Z добавлении на подгруппу , H группы G порожденную b при . Для всех a в H log _b   a существует . И наоборот , log _b   a не существует для a, входящего в H. не

Если H бесконечно групповой , то log _b   a также уникален, а дискретный логарифм представляет собой изоморфизм

$\log _{b}\colon H\to \mathbf {Z} .$

С другой стороны, если H конечна порядка n по сравнения , то log _b   a уникален только с точностью до модулю n , а дискретный логарифм представляет собой групповой изоморфизм

$\log _{b}\colon H\to \mathbf {Z} _{n},$

где Z _n обозначает аддитивную группу целых чисел по модулю n .

Знакомая формула замены основания для обыкновенных логарифмов остается в силе: если c — еще один генератор H , то

$\log _{c}a=\log _{c}b\cdot \log _{b}a.$

Алгоритмы

См. Также: Записи дискретного логарифма.

Нерешенная задача в информатике :

Можно ли вычислить дискретный логарифм за полиномиальное время на классическом компьютере?

(еще нерешенные проблемы по информатике)

Задача дискретного логарифмирования считается вычислительно неразрешимой. То есть в целом не известен эффективный классический алгоритм вычисления дискретных логарифмов.

Общий алгоритм вычисления log _b   a в конечных группах G заключается в возведении b во все большую и большую степень k искомое a до тех пор, пока не будет найдено . Этот алгоритм иногда называют пробным умножением . Для этого требуется время работы, линейное по размеру группы G и, следовательно, экспоненциальное по количеству цифр в размере группы. Следовательно, это алгоритм с экспоненциальным временем, практичный только для небольших групп G .

Существуют более сложные алгоритмы, обычно основанные на аналогичных алгоритмах факторизации целых чисел . Эти алгоритмы работают быстрее, чем наивный алгоритм, некоторые из них пропорциональны квадратному корню из размера группы и, таким образом, экспоненциально увеличивают вдвое количество цифр в размере группы. Однако ни один из них не работает за полиномиальное время (по количеству цифр в размере группы).

• Бэби-шаг, гигантский шаг
• Функциональное поле сита
• Алгоритм расчета индекса
• Сито числового поля
• Алгоритм Полига – Хеллмана
• Ро-алгоритм Полларда для логарифмов
• Алгоритм кенгуру Полларда (он же лямбда-алгоритм Полларда)

эффективный квантовый алгоритм принадлежит Питеру Шору .

Эффективные классические алгоритмы существуют и в некоторых частных случаях. Например, в группе сложенных целых чисел по модулю p степень b ^к становится произведением bk , а равенство означает сравнение модулю p целых чисел по . Расширенный алгоритм Евклида быстро находит k .

В случае Диффи-Хеллмана используется циклическая группа по модулю простого числа p , что позволяет эффективно вычислить дискретный логарифм с помощью Полига-Хеллмана, если порядок группы (то есть p -1) достаточно гладкий , то есть не имеет больших простых множителей .

Сравнение с целочисленной факторизацией

Хотя вычисление дискретных логарифмов и факторизация целых чисел представляют собой отдельные проблемы, у них есть некоторые общие свойства:

• оба являются частными случаями проблемы скрытых подгрупп для конечных абелевых групп ,
• обе задачи кажутся трудными (эффективных алгоритмов для неквантовых компьютеров не известно ),
• для обеих задач известны эффективные алгоритмы на квантовых компьютерах,
• алгоритмы одной задачи часто адаптируются к другой, и
• сложность обеих задач была использована для создания различных криптографических систем.

Криптография

Существуют группы, для которых вычисление дискретных логарифмов, по-видимому, затруднено. В некоторых случаях (например, большие подгруппы простого порядка групп Z _p ^× ) не только не существует эффективного алгоритма для наихудшего случая, но и сложность в среднем случае можно показать, что примерно такая же сложная, как и в наихудшем случае, с использованием случайной самосократимости .

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

Популярным выбором группы G в дискретной логарифмической криптографии (DLC) являются циклические группы Z _p ^× (например , шифрование Эль-Гамаля , обмен ключами Диффи-Хеллмана и алгоритм цифровой подписи ) и циклические подгруппы эллиптических кривых над конечными полями ( см. Криптография эллиптических кривых ).

Хотя общеизвестного алгоритма решения задачи дискретного логарифмирования в целом не существует, первые три шага алгоритма решета числового поля зависят только от группы G , а не от конкретных элементов G , конечный журнал которых требуется. Предварительно вычисляя эти три шага для конкретной группы, достаточно выполнить только последний шаг, который требует гораздо меньше вычислительных затрат, чем первые три, чтобы получить определенный логарифм в этой группе.

Оказывается, большая часть интернет- трафика использует одну из нескольких групп размером 1024 бита или меньше, например циклические группы с порядком простых чисел Окли, указанным в RFC 2409. Атака Logjam использовала эту уязвимость для компрометации различных интернет-сервисов, которые позволяли использовать группы, порядок которых представлял собой 512-битное простое число, так называемую экспортную степень .

По оценкам авторов атаки Logjam, гораздо более сложные предварительные вычисления, необходимые для решения проблемы дискретного журнала для 1024-битного простого числа, будут в пределах бюджета крупного национального разведывательного агентства, такого как Агентство национальной безопасности США (АНБ). Авторы Logjam предполагают, что предварительные вычисления на основе широко используемых 1024 простых чисел DH лежат в основе утверждений в просочившихся документах АНБ о том, что АНБ способно взломать большую часть современной криптографии.

См. также

• AW Фабер Модель 366
• Перси Ладгейт и ирландский логарифм

Ссылки

• Розен, Кеннет Х. (2011). Элементарная теория чисел и ее применение (6-е изд.). Пирсон. п. 368. ИСБН  978-0321500311 .
• Вайсштейн, Эрик В. «Дискретный логарифм» . Математический мир . Вольфрам Веб . Проверено 1 января 2019 г.

Дальнейшее чтение

• Ричард Крэндалл ; Карл Померанс . Глава 5, Простые числа: вычислительная перспектива , 2-е изд., Springer.
• Стинсон, Дуглас Роберт (2006). Криптография: теория и практика (3-е изд.). Лондон, Великобритания: CRC Press . ISBN  978-1-58488-508-5 .