Введение в криптографию
[an error occurred while processing this directive]

Дискретное логарифмирование - часть 4


Как было отмечено, каждое из чисел, стоящих в правой части сравнения (), не превосходит . Поэтому оно раскладывается в произведение не более простых сомножителей и, следовательно, каждое из сравнений () построенной системы содержит лишь отличных от нуля коэффициентов. Матрица системы сравнений будет разреженной, что позволяет применять для ее решения специальные методы с меньшей оценкой сложности, чем обычный гауссов метод исключения переменных.

Вместо перебора всех допустимых значений в [] предлагается использовать так называемое решето, отбрасывающее все пары этих чисел, для которых правая часть () заведомо не раскладывается в произведение малых простых сомножителей. Для каждого и каждой малой простой степени

Организованная правильным образом, эта процедура одновременно отбирает все нужные пары чисел и дает разложение на простые сомножители правых частей сравнений (32).

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

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

Наконец, на последнем этапе производится вычисление логарифмов всех чисел . Пусть  - простое число из интервала

Для любых целых чисел

(34)

Отметим, что правая часть этого сравнения не превосходит . Просеивая все числа из указанного интервала, можно найти такие, что числа и правая часть сравнения () состоят из простых сомножителей, не превосходящих . Тогда сравнение () позволяет вычислить . Вычисление при известных уже значениях требует

арифметических операций.

Существуют и другие способы построения соотношений (). В [] для этого используются вычисления в полях алгебраических чисел. В качестве множителей в соотношениях типа () используются не только простые числа, но и простые идеалы с небольшой нормой.

Задача вычисления дискретных логарифмов может рассматриваться также и в полях , состоящих из элементов, в мультипликативных группах классов вычетов , в группах точек эллиптических кривых и вообще в произвольных группах. С литературой по этому вопросу можно ознакомиться по работе [].

Next: 4.9. Заключение

Up: 4. Алгоритмические проблемы теории

Previous: 4.7. Как раскладывают составные

Contents:




- Начало -  - Назад -  - Вперед -


[an error occurred while processing this directive]