Алгоритм исчисления порядка (index-calculus algorithm) - вероятностный алгоритм вычисления дискретного алгоритма в кольце вычетов по модулю простого числа. Этот алгоритм подходит не для всех циклических групп.
История
Крайчик первым предложил идею данного алгоритма в 1922 году. После 1976 года задача дискретного логарифмирования становится важной для математики и криптоанализа. Это связано с созданием криптосистемы Диффи-Хелмана. В связи с этим в 1977 году Р.Меркле продемонстрировал идею алгоритма. Спустя два года он был впервые опубликован коллегами Меркеля. Наконец в 1979 году Адлерман оптимизировал его, исследовал трудоемкость и представил его в форме, которую мы знаем сейчас. В настоящее время алгоритм исчисления порядка и его улучшенные варианты дают наиболее быстрый способ вычисления дискретных логарифмов в некоторых конечных группах.
Постановка задачи дискретного логарифмирования
Для заданного простого числа и двух целых чисел и требуется найти целое число , удовлетворяющее сравнению:
где является элементом циклической группы , порожденной элементом .
Алгоритм
Пример
G=Z*71, g=7, a=17, n=φ(71)=70.
S={2, 3, 5, 7} (Шаг 1). (Можем сразу указать log77 mod 70=1).
Теперь будем перебирать k для составления системы сравнений вида * (Шаги 2—5).
k=2, 72 mod 71=49=7·7. (поскольку log77 уже вычислен, это сравнение нам не пригодится).
k=3, 73 mod 71=59.
k=4, 74 mod 71=58=2·29.
k=5, 75 mod 71=51=3·17.
k=6, 76 mod 71=2 6≡log72(mod 70)
k=7, 77 mod 71=14=2·7 7≡log72+log77(mod 70)
k=8, 78 mod 71=27=33 8≡3log73(mod 70)
k=9, 79 mod 71=47.
k=10, 710 mod 71=45=32·5 10≡2log73+log75(mod 70)
Теперь имеем достаточно сравнений для того, чтобы определить логарифмы от элементов факторной базы. Вот эти сравнения:
6≡log72(mod 70)
7≡log72+log77(mod 70)
8≡3log73(mod 70)
10≡2log73+log75(mod 70)
Решая полученную систему, получаем (Шаг 6):
log72≡6(mod 70), log73≡26(mod 70),
log75≡28(mod 70), log77≡1(mod 70).
Перейдем к Шагам 7—9:
k=1, 26·7 mod 71=40=23·5 log726≡3log72+log75—1(mod 70)
log726≡3·6+28—1(mod 70)
log726≡45(mod 70)
Проверка:
745 mod 71 = 26. Верно.
Ответ:
log726≡45(mod 70).
Замечание
Для случая G=Zp и для случая G=F2m составляет Lq[1/2,c], где q есть мощность G, с > 0 – константа.