Лекция: Отсюда получаем .

Метод линейного решета.Этот метод является развитием индекс – метода в следующих направлениях:

1) ускоряют решение системы линейных сравнений по mod (p-1), с помощью алгоритма Видемана предназначенного для решения системы линейных уравнений над полем с разреженной матрицей;

2) уменьшают величину чисел, которые требуется проверять на гладкость (и тем самым увеличить вероятность гладкости);

3) избавляются от пробных делений при проверке на гладкость. Используют другие более эффективные способы проверки чисел на гладкость.

Асимптотическую оценку сложности построенного метода линейного решета для вычисления дискретных логарифмов в при. проводят в предположении

и

при любом фиксированном, при .

Доказывают, что

1) разреженную систему линейных сравнений по mod (p-1) относительно неизвестных, и, можно решить методом Видемана за

=

операций по mod (p-1).

2) общая сложность вычисления логарифмов элементов специально построенной факторной базы выражается величиной

операций для любого фиксированного e > 0.

На последнем этапе метода линейного решета выражают искомый логарифм x через уже найденные логарифмы элементов факторной базы с оценкой сложности [2]

.

Литература

1. Adleman L.M. A subexponentional algorithm for the discrete logarithm problem with applications to cryptography. Proceedigs of the IEEE 20th Annual Symposium on Foundations of Computer Science, 1979. – 55-60.

2. Menezes A.J. van Oorschot P.C. Vanstone S.A. Handbook of applied cgyptography. CRC Press, NY, 1997.

3. Coppersmith D., Odlyzko A.M., Schroeppel R. Discrete logarithms in GF(p). Algorithmica. – 1986. – 1. – c. 1-15.

Глава 51.