~~~~~~~~~~~~~~~~~~~~ Arc.Ask3.Ru ~~~~~~~~~~~~~~~~~~~~~ 
Номер скриншота №:
✰ 2996CFE306D5CE5393E83681FD65DEA0__1707693660 ✰
Заголовок документа оригинал.:
✰ Discrete logarithm - Wikipedia ✰
Заголовок документа перевод.:
✰ Дискретный логарифм — Википедия ✰
Снимок документа находящегося по адресу (URL):
✰ https://en.wikipedia.org/wiki/Discrete_logarithm ✰
Адрес хранения снимка оригинал (URL):
✰ https://arc.ask3.ru/arc/aa/29/a0/2996cfe306d5ce5393e83681fd65dea0.html ✰
Адрес хранения снимка перевод (URL):
✰ https://arc.ask3.ru/arc/aa/29/a0/2996cfe306d5ce5393e83681fd65dea0__translat.html ✰
Дата и время сохранения документа:
✰ 08.06.2024 21:37:11 (GMT+3, MSK) ✰
Дата и время изменения документа (по данным источника):
✰ 12 February 2024, at 02:21 (UTC). ✰ 

~~~~~~~~~~~~~~~~~~~~~~ Ask3.Ru ~~~~~~~~~~~~~~~~~~~~~~ 
Сервисы Ask3.ru: 
 Архив документов (Снимки документов, в формате HTML, PDF, PNG - подписанные ЭЦП, доказывающие существование документа в момент подписи. Перевод сохраненных документов на русский язык.)https://arc.ask3.ruОтветы на вопросы (Сервис ответов на вопросы, в основном, научной направленности)https://ask3.ru/answer2questionТоварный сопоставитель (Сервис сравнения и выбора товаров) ✰✰
✰ https://ask3.ru/product2collationПартнерыhttps://comrades.ask3.ru


Совет. Чтобы искать на странице, нажмите Ctrl+F или ⌘-F (для MacOS) и введите запрос в поле поиска.
Дискретный логарифм Jump to content

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

Из Википедии, бесплатной энциклопедии

В математике для данных действительных чисел 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) над тщательно выбранными группами не имеет эффективного решения. [1]

Определение [ править ]

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

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

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

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

Степени 10 [ править ]

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

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

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

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

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

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

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

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

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

Дискретный логарифм — это просто обратная операция. Например, рассмотрим уравнение 3 к ≡ 13 (по модулю 17). В приведенном выше примере одно решение — k = 4, но это не единственное решение. С 3 16 ≡ 1 (mod 17) — как следует из малой теоремы Ферма — отсюда также следует, что если n — целое число, то 3 4+16 н ≡ 3 4 × (3 16 ) н ≡ 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 к + л = б к б л . [2] Другими словами, функция

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

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

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

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

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

Алгоритмы [ править ]

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

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

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

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

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

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

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

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

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

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

Криптография [ править ]

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

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

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

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

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

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

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

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

  1. ^ Менезес, AJ; ван Ооршот, ПК; Ванстон, С.А. «Глава 8.4 Шифрование с открытым ключом Эль-Гамаля» (PDF) . Справочник по прикладной криптографии . ЦРК Пресс .
  2. ^ Перейти обратно: а б Лам; Шпарлинский; Ван; Син (2001). Лам, Квок-Ян; Шпарлинский, Игорь; Ван, Хуасюн; Син, Чаопин (ред.). Криптография и вычислительная теория чисел . Прогресс в области информатики и прикладной логики (1-е изд.). Биркхойзер Базель . стр. 54–56. дои : 10.1007/978-3-0348-8295-8 . eISSN   2297-0584 . ISBN  978-3-7643-6510-3 . ISSN   2297-0576 .
  3. ^ Шор, Питер (1997). «Алгоритмы полиномиального времени для простой факторизации и дискретных логарифмов на квантовом компьютере». SIAM Journal по вычислительной технике . 26 (5): 1484–1509. arXiv : Quant-ph/9508027 . дои : 10.1137/s0097539795293172 . МР   1471990 . S2CID   2337707 .
  4. ^ Блейк, Ян Ф.; Гарефалакис, Тео (1 апреля 2004 г.). «О сложности дискретного логарифма и задач Диффи–Хеллмана» . Журнал сложности . Festschrift для Харальда Нидеррайтера, специальный выпуск по кодированию и криптографии. 20 (2): 148–170. дои : 10.1016/j.jco.2004.01.002 . ISSN   0885-064X .
  5. ^ Перейти обратно: а б с Адриан, Дэвид; Бхаргаван, Картикеян; Дурумерик, Закир; Годри, Пьеррик; Грин, Мэтью; Халдерман, Дж. Алекс; Хенингер, Надя ; Спринголл, Дрю; Томе, Эммануэль; Валента, Люк; ВандерСлот, Бенджамин; Вустроу, Эрик; Занелла-Бегелен, Сантьяго; Циммерманн, Пол (октябрь 2015 г.). «Несовершенная прямая секретность: как Диффи-Хеллман терпит неудачу на практике» (PDF) .
  6. ^ Харкинс, Д.; Каррел, Д. (ноябрь 1998 г.). «Интернет-обмен ключами (IKE)» . Сетевая рабочая группа . дои : 10.17487/RFC2409 . ISSN   2070-1721 .
  • Розен, Кеннет Х. (2011). Элементарная теория чисел и ее применение (6-е изд.). Пирсон. п. 368. ИСБН  978-0321500311 .
  • Вайсштейн, Эрик В. «Дискретный логарифм» . Математический мир . Вольфрам Веб . Проверено 1 января 2019 г.

Дальнейшее чтение [ править ]

Arc.Ask3.Ru: конец оригинального документа.
Arc.Ask3.Ru
Номер скриншота №: 2996CFE306D5CE5393E83681FD65DEA0__1707693660
URL1:https://en.wikipedia.org/wiki/Discrete_logarithm
Заголовок, (Title) документа по адресу, URL1:
Discrete logarithm - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть, любые претензии не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, денежную единицу можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)