Навигация
Задача вычисления дискретного логарифма в мультипликативной группе конечного поля
42383
знака
0
таблиц
0
изображений
1. Задача вычисления дискретного логарифма в мультипликативной группе конечного поля
Практически сразу после опубликования работы У. Диффи и М. Хеллмана Дж. Поллард публикует вероятностные алгоритмы решения задачи дискретного логарифмирования, имеющие корневую оценку сложности и не требующие большого объема памяти [18]. Этот метод называют r-методом Полларда (вариация метода - l-метод Полларда, общая идея известна также под названием "baby step, giant step").
В дальнейшем основные идеи построения эффективных алгоритмов для решения задачи дискретного логарифмирования были связаны с, так называемым, методом решета. Долгое время асимптотически наиболее эффективным (асимптотическая оценка сложности -
, оставался метод Д. Копперсмита, А. Одлыжко, Р. Шрёппеля [19]. Метод был реализован и применен для логарифмирования в простых полях при p длиной до 67 десятичных знаков.
Последним существенным достижением в этой области является метод решета числового поля Д. Гордона [20]. Асимптотически метод более эффективен, чем все предыдущие: оценка его трудоемкости. Однако его практическая реализация сложнее: пока имеется сообщение, что этим методом удалось решить задачу дискретного логарифмирования в простом поле при p длиной 40 десятичных знаков. Для этого специалистам немецкого университета Universitat des Saarlandes в Саарбрюккене потребовались 21 час работы рабочей станции Sparc и 40 минут работы суперкомпьютера Cray [21]. По последним данным 1997 года немецким исследователям удалось реализовать процедуру логарифмирования для чисел длиной 85 десятичных знаков.
За каждым из названных методов стоит целый спектр их модификаций и вариантов. Из отечественных исследователей, работающих в этом направлении необходимо назвать О. Н. Василенко и И. А. Семаева. В тезисах выступлений последнего на конференциях по теории чисел и ее приложениям (Тула, Воронеж) содержатся весьма интересные новые идеи в развитие метода решета.
Исследователи постоянно предпринимают попытки поиска принципиально иных подходов (отличных от идей метода решета) к задаче дискретного логарифмирования. Из опубликованного здесь следует упомянуть работы, связанные с попыткой использования частных Ферма [22], [23], однако, пока успешное логарифмирование этим методом требует большего объема информации, чем "классическая" постановка задачи.
Также следует упомянуть о том, что с середины 1997 года в научной среде циркулируют слухи о том, что российскому ученому С. А. Степанову удалось построить полиномиальный алгоритм дискретного логарифмирования. Однако, вплоть до сегодняшнего дня убедительные подтверждения этому факту отсутствуют, впрочем, как и убедительные опровержения.
2. Задача разложения целых чисел на множители
По сравнению с задачей дискретного логарифмирования задача факторизации чисел или разложения их на множители имеет более длительную историю, ведомую обычно с античных времен от Эратосфена (предположительно 284 - 202 гг. до н.э.), а в дальнейшем связанную с именами таких великих математиков, как Фибоначчи (предположительно 1180-1250 гг.), Ферма (1601-1665 гг.), Эйлер (1707-1783 гг.), Лежандр (1752-1833 гг.), Гаусс (1777-1855 гг.). В большинстве случаев удается разложить число на множители с помощью пробных делений на первые (маленькие) простые числа. Задача становится содержательной, когда требуется разложить число, равное произведению двух больших простых чисел (например, число Блюма). В 70-х годах был предложен (p-1)-метод Полларда [24], эффективный для случая, когда p-1 раскладывается на маленькие простые множители, где p - один из делителей факторизуемого числа. Вскоре, как развитие данного решения появился (p+1)-метод Полларда. Следующим шагом в этом направлении стала идея использования псевдослучайных отображений (r-метод Полларда). Этим методом было разложено на множители 8-ое число Ферма (- число длиной 77 десятичных знаков). Дальнейшее развитие этих идей вылилось в методы с использованием группы точек эллиптической кривой [25].
На сегодняшний день, как и для задачи дискретного логарифмирования, основные продвижения в проблеме факторизации связаны с развитием методов решета, в которых выделяют следующие этапы развития: методы линейного решета, методы квадратичного решета [26] и метод решета числового поля [27], [28]. Сегодня практически наиболее эффективным для факторизации чисел длиной до 130 десятичных знаков остается метод квадратичного решета. Его асимптотическая оценка трудоемкости - , где
. Именно этим методом был решен предложенный Райвестом практический пример вскрытия системы RSA [29], для чего потребовалось разложить на множители число длиной 129 десятичных знаков.
Методы решета числового поля асимптотически более эффективны (оценка трудоемкости:), но применимы только для чисел вида n=re-s, где r и s сравнительно малы. На практике считается, что рассматриваемые методы следует применять для чисел из интервала 10130<n<10160. Именно таким образом в 1993 году были получены рекордные разложения: 9-ое число Ферма (2512+1 - длина 155 десятичных знаков); 2523-1 - длина 159 десятичных знаков.
Как уже было сказано выше, новые идеи в развитие метода решета содержатся в работах И. А. Семаева, что позволяет надеяться на дальнейший прогресс в данной проблематике.
Похожие работы
... , что делает использование нейропроцессоров нерентабельным. Однако аналогичная проблема раньше стояла и перед обычными компьютерами, поэтому следует ожидать, что нейровычислители станут доступнее. 3. Квантовые компьютеры Квантовый компьютер - вычислительное устройство, которое путём выполнения квантовых алгоритмов существенно использует при работе квантовомеханические эффекты, такие как ...
... подчеркнули, что данные довольно условны, поскольку бизнес-модели электронной платежной системы различны и их нельзя сравнивать напрямую. По мнению CNews Analytics, такую положительную динамику развития электронных платежных систем в России обеспечивают ряд факторов: · Во-первых, это рост доходов населения и увеличение числа пользователей сотовой связи. Действительно, оплата услуг мобильной ...
... «электронные деньги», раскрыть сущность и содержание электронных денег через изучение их природы и функций. Анализ состояния рынка электронных денег в Российской Федерации и на западе, и определение основных тенденций развития рынка цифровой наличности. Изучив рынок электронных денег, мы можем сделать несколько основных выводов: Обращение электронных денег вызывает появление рисков на макро- ...
... 6.0. – Microsoft Press, 1998. – 260 c. ISBN 1-57231-961-5 ТУЛЬСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ На правах рукописи Карпов Андрей Николаевич ЗАЩИТА ИНФОРМАЦИИ В СИСТЕМАХ ДИСТАНЦИОННОГО ОБУЧЕНИЯ С МОНОПОЛЬНЫМ ДОСТУПОМ Направление 553000 - Системный анализ и управление Программная подготовка 553005 – Системный анализ данных и моделей принятия решений АВТОРЕФЕРАТ диссертации на соискание степени ...
0 комментариев