02.01.2023

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


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

История

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

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

Для заданного простого числа p {displaystyle p} и двух целых чисел g {displaystyle g} и c {displaystyle c} требуется найти целое число x {displaystyle x} , удовлетворяющее сравнению:

где c {displaystyle c} является элементом циклической группы G {displaystyle G} , порожденной элементом g {displaystyle g} .

Алгоритм

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

Задача: найти x такое, что g x ≡ c {displaystyle g^{x}equiv c} .

  • Выбираем факторную базу S = {p1, p2, p3, …, pt} (Если G = Z*p, то база состоит из t первых простых чисел).
  • Возводим g в случайную степень k, где k такое, что 0 ⩽ k < n {displaystyle 0leqslant k<n} . Получаем g k {displaystyle g^{k}} .
  • Представляем gk следующим образом: g k = ∏ i = 1 t p i a i , {displaystyle g^{k}=prod _{i=1}^{t}p_{i}^{a_{i}},} где a i ⩾ 0 {displaystyle a_{i}geqslant 0} (то есть пытаемся разложить его по факторной базе). Если не получается, то возвращаемся ко 2-му пункту.
  • Из пункта 3 следует выражение k ≡ ∑ i = 1 t a i log g ⁡ p i mod n , {displaystyle kequiv sum _{i=1}^{t}a_{i}log _{g}p_{i}mod n,} полученное путём логарифмирования (берётся сравнение по модулю порядка группы, так как мы работаем с показателем степени, а g n ≡ 1 {displaystyle g^{n}equiv 1} в группе G). В этом выражении неизвестны логарифмы. Их t штук. Необходимо получить таких уравнений t + c штук, если этого не возможно сделать, возвращаемся к пункту 2 (при реализации на компьютере) или получить необходимое количество уравнений, чтобы найти все неизвестные логарифмы (при решении человеком).
  • Решаем получившуюся систему уравнений, с t неизвестными и t + c сравнениями.
  • Выбираем случайное число k такое, что 0 ⩽ k < n {displaystyle 0leqslant k<n} . Вычисляем c g k {displaystyle cg^{k}} .
  • Повторяем пункт 3, только для числа c g k {displaystyle cg^{k}} . Если не получается, то возвращаемся к 6-му пункту.
  • Аналогично пункту 4, получаем: x = log g ⁡ c = ∑ i = 1 t a i log g ⁡ p i − k mod n {displaystyle x=log _{g}c=sum _{i=1}^{t}a_{i}log _{g}p_{i}-kmod n} , где log g ⁡ p i {displaystyle log _{g}p_{i}} ( 1 ⩽ i ⩽ t {displaystyle 1leqslant ileqslant t} ), где k = log g ⁡ g k mod n {displaystyle k=log _{g}g^{k}mod n} . В этом пункте мы и решили задачу дискретного логарифма, отыскав x = log g ⁡ c {displaystyle x=log _{g}c} .
  • Выход: x = log g ⁡ c {displaystyle x=log _{g}c} .

    Пример

    Решить уравнение: 17 ≡ 10 x ( m o d 47 ) {displaystyle 17equiv 10^{x};(mod47)}

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

    k = 1 10 1 m o d 47 = 10 = 2 ∗ 5 {displaystyle k=1;;;;10^{1}mod47=10=2*5}

    k = 2 10 2 m o d 47 ≡ 6 = 2 ∗ 3 {displaystyle k=2;;;;10^{2}mod47equiv 6=2*3}

    k = 3 10 3 m o d 47 ≡ 13 {displaystyle k=3;;;;10^{3}mod47equiv 13}

    k = 4 10 4 m o d 47 ≡ 36 = 2 ∗ 2 ∗ 3 ∗ 3 {displaystyle k=4;;;;10^{4}mod47equiv 36=2*2*3*3}

    k = 5 10 5 m o d 47 ≡ 31 {displaystyle k=5;;;;10^{5}mod47equiv 31}

    k = 6 10 6 m o d 47 ≡ 28 = 2 ∗ 2 ∗ 7 {displaystyle k=6;;;;10^{6}mod47equiv 28=2*2*7}

    k = 7 10 7 m o d 47 ≡ 45 = 3 ∗ 3 ∗ 5 {displaystyle k=7;;;;10^{7}mod47equiv 45=3*3*5}

    Логарифмируем и обозначаем U i = l o g g p i {displaystyle U_{i}=log_{g}p_{i}} И получаем систему уравнений { U 1 + U 3 = 1 U 1 + U 2 = 2 2 U 1 + 2 U 2 = 4 2 U 2 + U 3 = 7 {displaystyle left{{egin{matrix}U_{1}+U_{3}=1U_{1}+U_{2}=22U_{1}+2U_{2}=42U_{2}+U_{3}=7end{matrix}} ight.}

    Решаем её

    u 2 = 8 3 ( m o d 46 ) = 8 ∗ 3 − 1 ( m o d 46 ) = { φ ( 46 ) = φ ( 2 ∗ 23 ) } = 22 = 8 ∗ 3 22 ( m o d 46 ) ≡ 18 {displaystyle u_{2}={frac {8}{3}}(mod46)=8*3^{-1}(mod46)={varphi (46)=varphi (2*23)}=22=8*3^{22}(mod46)equiv 18}

    Действительно, 10 18 m o d 47 ≡ 3 {displaystyle 10^{18}mod47equiv 3} , следовательно U 1 = 30 {displaystyle U_{1}=30} , U 2 = 18 {displaystyle U_{2}=18} , U 3 = 17 {displaystyle U_{3}=17}

    Находим k такое, чтобы c g k = ∏ i = 1 t p i a i {displaystyle cg^{k}={displaystyle prod _{i=1}^{t}p_{i}^{a_{i}}}}

    17 ∗ 10 1 ( m o d 47 ) = 29 {displaystyle 17*10^{1}(mod47)=29}

    17 ∗ 10 2 ( m o d 47 ) = 8 = 2 ∗ 2 ∗ 2 {displaystyle 17*10^{2}(mod47)=8=2*2*2}

    Следовательно k = 2 {displaystyle k=2}

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

    l o g a 17 = [ ( l o g a 2 + l o g a 2 + l o g a 2 ) − 2 ] m o d 46 = ( 3 ∗ 30 − 2 ) m o d 46 ≡ 42 {displaystyle log_{a}17=[(log_{a}2+log_{a}2+log_{a}2)-2]mod46=(3*30-2)mod46equiv 42}

    Ответ: x = 42 {displaystyle x=42}

    Сложность

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

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

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

    Сложность

    Вычислительная сложность снижена до O ( 2 l o g 2 ( p ) ) {displaystyle O(2log_{2}(p))} , по сравнению с оригинальном алгоритмом.


    Похожие новости:

    Алгоритм быстрой оболочки

    Алгоритм быстрой оболочки
    Алгоритм быстрой оболочки — алгоритм построения выпуклой оболочки на плоскости. Использует идею быстрой сортировки Хоара Описание Множество точек разбивается на два подмножества, каждое из

    Гимади, Эдуард Хайрутдинович

    Гимади, Эдуард Хайрутдинович
    Гимади, Эдуард Хайрутдинович (4 января 1937) — доктор физ.-мат. наук, профессор, ведущий научный сотрудник, заведующий лабораторией дискретных экстремальных задач Института математики СО РАН. Автор

    Алгоритм Монтгомери (эллиптические кривые)

    Алгоритм Монтгомери (эллиптические кривые)
    Алгоритм Монтгомери(англ. Montgomery ladder) — это алгоритм, позволяющий проводить операцию скалярного умножения для произвольной точки, принадлежащей эллиптической кривой за конечное время.

    Алгоритм Кнута — Морриса — Пратта

    Алгоритм Кнута — Морриса — Пратта
    Алгоритм Кнута — Морриса — Пратта (КМП-алгоритм) — эффективный алгоритм, осуществляющий поиск подстроки в строке. Время работы алгоритма линейно зависит от объёма входных данных, то есть разработать
    Комментариев пока еще нет. Вы можете стать первым!

    Добавить комментарий!

    Ваше Имя:
    Ваш E-Mail:
    Введите два слова, показанных на изображении: *
    Популярные новости
    Квартиры в современных новостройках – ЖК Весна
    Квартиры в современных новостройках – ЖК Весна
    Новостройки – это целый пласт рынка недвижимости, набирающий все большую популярность....
    Проект ПМООС: когда и для чего необходим
    Проект ПМООС: когда и для чего необходим
    ПМООС – специализированный раздел строительного проекта, предполагающий информационную документацию...
    Климатическая техника Russia-Gree
    Климатическая техника Russia-Gree
    Компания по продаже качественной климатической техники Russia-Gree предлагает потребителям широкий...
    Все новости