Немецкие ученые успешно решили проблему дискретного логарифмирования по модулю 530-битного простого числа p

Немецкие ученые успешно решили проблему дискретного логарифмирования по модулю 530-битного (160 десятичных знаков) простого числа p. Предполагаемая сложность вычисления дискретных логарифмов лежит в основе многих криптографических алгоритмов, например, протокола Диффи-Хелмана для выработки общего секрета (ключа). Таким образом, представленный результат позволяет лучше оценить криптографическую стойкость и безопасные параметры для таких алгоритмов.

Из соображений беспристрастности простое число p было выбрано из последовательных цифр числа "пи" так, чтобы оно также удовлетворяло стандартным криптографическим требованиям, усложняющим дискретное логарифмирование. Для вычисления дискретного логарифма был использован алгоритм Общего Решета Числового Поля (General Number Field Sieve, GNFS), который является на данный момент лучшим из известных (как впрочем, и для задачи факторизации больших чисел). Вычисления производились на множестве компьютеров в Институте Численного Моделирования и в Математическом Институте университета Бонна, в том числе и на кластере Himalaya (128 x dual-Xeon EM64T) под управлением Ubuntu 6.06 LTS с ядром 2.6.15 (64 bit). Кластер параллельно выполнял до 8 задач, каждая из которых использовала от 12 до 24 процессоров. На одиночном 3.2 GHz Xeon64 PC этот же объем работ потребовал бы около 17 лет.