Введение
Алгоритм решения проблемы дискретного логарифма
В теории групп, области математики, метод «маленький шаг — большой шаг» является алгоритмом типа «встреча посередине» для вычисления дискретного логарифма или порядка элемента в конечной абелевой группе, разработанный Дэниелом Шенксом. Проблема дискретного логарифма имеет фундаментальное значение для области криптографии с открытым ключом. Многие из наиболее распространенных криптографических систем основаны на предположении, что вычисление дискретного логарифма чрезвычайно сложно; чем сложнее это вычисление, тем выше уровень безопасности при передаче данных. Один из способов повышения сложности проблемы дискретного логарифма — построение криптосистемы на основе группы большего размера.
In group theory, a branch of mathematics, the baby step giant step is a meet in the middle algorithm for computing the discrete logarithm or order of an element in a finite abelian group by Daniel Shanks. The discrete log problem is of fundamental importance to the area of public key cryptography. Many of the most commonly used cryptography systems are based on the assumption that the discrete log is extremely difficult to compute; the more difficult it is, the more security it provides a data transfer. One way to increase the difficulty of the discrete log problem is to base the cryptosystem on a larger group.
На практике
Лучший способ ускорить алгоритм "маленький шаг, гигантский шаг" — использовать эффективную схему поиска по таблице. В этом случае оптимальным решением является хеш-таблица. Хеширование выполняется по второму компоненту, и для проверки на шаге 1 основного цикла γ хешируется и проверяется полученный адрес памяти. Поскольку хеш-таблицы позволяют извлекать и добавлять элементы за время O(1) (константное время), это не замедляет работу алгоритма "маленький шаг, гигантский шаг" в целом. Пространственная сложность алгоритма составляет O(p), а временная сложность — O(√p). Это время выполнения лучше, чем время выполнения наивного перебора. Алгоритм "маленький шаг, гигантский шаг" может быть использован злоумышленником для получения секретного ключа, сгенерированного при обмене ключами Диффи — Хеллмана, если модуль является простым числом не слишком большого размера. Если модуль не является простым, алгоритм Полига — Хеллмана имеет меньшую вычислительную сложность и потенциально решает ту же задачу.