Аннотация:
Для задачи дискретного логарифмирования в конечном простом поле предложен ускоренный алгоритм построения разреженной системы уравнений методом линейного решета. Исследована трудоемкость решения указанной системы методом Ланцоша. Получены оценки сложности для последовательной и параллельной модели вычислений. Все алгоритмы были запрограммированы. Приводятся времена вычисления логарифмов для простых полей с модулями логарифмирования размера до 60 десятичных знаков.