Ро-метод Полларда для нахождения дискретного логарифма в случае его малого веса

Информационные технологии. 2022. Т. 28. № 1. С. 26–32.

Черепнев М. А., Грачева С. С.

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

Криптографические методы основаны на математических преобразованиях оцифрованных текстов. Важное значение для криптографии при этом имеет функция дискретного логарифмирования.

В статье представлена модификация ро-метода Полларда для поиска дискретного логарифма в случае, когда он выражается бинарным вектором относительно малого веса.

Предлагаемый алгоритм может быть эффективно применен на достаточно большом числе вычислительных узлов. В работе рассматривается случай, когда известно некоторое близкое приближение дискретного логарифма. Для формирования алгоритма использованы оценки на биномиальные коэффициенты и теорема Берри—Эссеена для схемы Бернулли.

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