Русская Википедия:Алгоритм исчисления порядка

Материал из Онлайн справочника
Версия от 11:51, 19 июля 2023; EducationBot (обсуждение | вклад) (Новая страница: «{{Русская Википедия/Панель перехода}} '''Алгоритм исчисления порядка''' (''index-calculus algorithm'') — вероятностный алгоритм вычисления дискретного логарифма в кольце вычетов по модулю Простое число|простого чи...»)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)
Перейти к навигацииПерейти к поиску

Алгоритм исчисления порядка (index-calculus algorithm) — вероятностный алгоритм вычисления дискретного логарифма в кольце вычетов по модулю простого числа. На сложности нахождения дискретного логарифма основано множество алгоритмов связанных с криптографией. Так как для решения данной задачи с использованием больших чисел требуется большое количество ресурсов, предоставить которые не может ни один современный компьютер. Примером такого алгоритма является ГОСТ Р 34.10-2012.

История

Маурис Крайчик первым предложил основную идею данного алгоритма в своей книге «Théorie des Nombres» в 1922 году. После 1976 года задача дискретного логарифмирования становится важной для математики и криптоанализа. Это связано с созданием криптосистемы Диффи-Хелмана. В связи с этим в 1977 году Р.Меркле возобновил обсуждения данного алгоритма. Спустя два года он был впервые опубликован коллегами Меркеля. Наконец в 1979 году Адлерман оптимизировал его, исследовал трудоемкость и представил его в форме, которую мы знаем сейчас. В настоящее время алгоритм исчисления порядка и его улучшенные варианты дают наиболее быстрый способ вычисления дискретных логарифмов в некоторых конечных группах.

Постановка задачи дискретного логарифмирования

Для заданного простого числа <math>p </math> и двух целых чисел <math>g </math> и <math>c </math> требуется найти целое число <math>x </math>, удовлетворяющее сравнению:Шаблон:Формула

где <math>c </math> является элементом циклической группы <math>G </math>, порожденной элементом <math>g </math>.

Алгоритм

Вход: g — генератор циклической группы порядка n, a — из циклической подгруппы, p — простое число, c — параметр надёжности, обычно берут равным 10 или близкое к этому значению число (используется для реализации алгоритма на компьютере, если решает человек, то его не задают).

Задача: найти x такое, что <math>g^x \equiv c</math>.

  1. Выбираем факторную базу S = {p1, p2, p3, …, pt} (Если G = Z*p, то база состоит из t первых простых чисел).
  2. Возводим g в случайную степень k, где k такое, что <math>0 \leqslant k < n </math>. Получаем <math>g^k</math>.
  3. Представляем gk следующим образом:
    <math> g^k = \prod_{i=1}^{t} p^{a_i}_i,</math>
    где <math>a_i \geqslant 0</math> (то есть пытаемся разложить его по факторной базе). Если не получается, то возвращаемся ко 2-му пункту.
  4. Из пункта 3 следует выражение
    <math> k \equiv \sum_{i=1}^t a_i \log_g p_i \mod n,</math>
    полученное путём логарифмирования (берётся сравнение по модулю порядка группы, так как мы работаем с показателем степени, а <math>g^n \equiv 1</math> в группе G). В этом выражении неизвестны логарифмы. Их t штук. Необходимо получить таких уравнений t + c штук, если этого не возможно сделать, возвращаемся к пункту 2 (при реализации на компьютере) или получить необходимое количество уравнений, чтобы найти все неизвестные логарифмы (при решении человеком).
  5. Решаем получившуюся систему уравнений, с t неизвестными и t + c сравнениями.
  6. Выбираем случайное число k такое, что <math>0 \leqslant k < n </math>. Вычисляем <math>cg^k</math>.
  7. Повторяем пункт 3, только для числа <math>cg^k</math>. Если не получается, то возвращаемся к 6-му пункту.
  8. Аналогично пункту 4, получаем:
    <math> x = \log_gc = \sum_{i=1}^t a_i \log_g p_i - k \mod n</math>, где <math>\log_g p_i</math> (<math>1 \leqslant i \leqslant t</math>), где <math>k = \log _g g^k \mod n</math>. В этом пункте мы и решили задачу дискретного логарифма, отыскав <math> x = \log_g c</math>.

Выход: <math> x = \log_g c</math>.

Пример

Решить уравнение: <math>17 \equiv 10^x\;(mod47)</math>

Выбираем факторную базу <math> S = \{2,3,5\}</math> Пусть k = 7 Вычисляем <math>g^k</math>

<math> k = 1 \;\;\;\; 10^1 mod 47 = 10 = 2 * 5</math>

<math> k = 2 \;\;\;\; 10^2 mod 47 \equiv 6 = 2 * 3</math>

<math> k = 3 \;\;\;\; 10^3 mod 47 \equiv 13 </math>

<math> k = 4 \;\;\;\; 10^4 mod 47 \equiv 36 = 2 * 2 * 3 * 3</math>

<math> k = 5 \;\;\;\; 10^5 mod 47 \equiv 31</math>

<math> k = 6 \;\;\;\; 10^6 mod 47 \equiv 28 = 2 * 2* 7</math>

<math> k = 7 \;\;\;\; 10^7 mod 47 \equiv 45 = 3 * 3 * 5</math>

Логарифмируем и обозначаем <math>U_i = log_gp_i</math> И получаем систему уравнений <math>\left\{\begin{matrix}U_1+U_3 = 1 \\ U_1 + U_2 = 2 \\ 2U_1 + 2U_2 = 4 \\ 2U_2 + U_3 = 7\end{matrix}\right.</math>

Решаем её

<math>u_2 = \frac{8}{3} (mod46) = 8*3^{-1}(mod46) = \{\varphi(46) = \varphi(2*23)\} = 22 = 8*3^{22}(mod46)\equiv 18</math>

Действительно, <math>10^{18} mod47 \equiv 3</math>, следовательно <math>U_1 = 30</math>, <math>U_2 = 18</math>, <math>U_3 = 17</math>

Находим k такое, чтобы <math> cg^k = {\displaystyle\prod_{i=1}^{t} p^{a_i}_i}</math>

<math> 17 * 10^1 (mod47) = 29</math>

<math> 17 * 10 ^2 (mod47) = 8 = 2 * 2 * 2</math>

Следовательно <math> k = 2 </math>

Логарифмируем данное выражение и получаем

<math> log_a17 = [(log_a2 + log_a2 + log_a2) -2] mod46 = (3*30 - 2)mod 46 \equiv 42</math>

Ответ: <math> x = 42 </math>

Сложность

В данном алгоритме, количество итераций зависит, как от размера p, так и от размера факторной базы. Но факторную базу мы выбираем заранее, и её размер является фиксированным. Поэтому итоговая сложность определяется только размером простого числа и равняется: <math> O(c_1*2^{(c_2 + o(1))\sqrt{logp\;loglogp}})</math> , где <math>c_1</math>,<math>c_2</math> — некоторые константы, зависящие от промежуточных вычислений, в частности, от выбора факторной базы.

Усовершенствования

Ускоренный алгоритм исчисления порядка, суть которого состоит в том, чтобы использовать таблицу индексов.

Сложность

Вычислительная сложность снижена до <math>O(2log_2(p))</math>, по сравнению с оригинальном алгоритмом.

См. также

Ссылки

Шаблон:Rq

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Алгоритм_исчисления_порядка&oldid=8940290