Метод Лемана

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

Метод Лемана[править | править код]

Метод Лемана развивает идеи, заложенные в методе факторизации Ферма, и ищет делители числа , используя равенство для некоторого целого числа . Он основан на следующей теореме.[2]


Формулировка теоремы[1]

Предположим, что  — положительное нечетное целое, а  — целое такое, что . Если , где и простые и

,

тогда существуют такие неотрицательные целые числа , и , что

,
,
, если нечетное,

и

.

Если  — простое, таких чисел , и не существует.

Модифицированный метод Лемана[править | править код]

Формулировка теоремы[править | править код]

Пусть составное число, являющееся произведением двух нечётных взаимно простых чисел, удовлетворяющих неравенствам . Тогда, найдутся натуральные числа и такие, что

1. Выполнено равенство при ,
2. Выполнено неравенство .[2] Для доказательства данной теоремы нам потребуется следующая Лемма.

Лемма[править | править код]

Пусть выполнены условия Теоремы. Тогда найдутся натуральные числа такие что и .[3]

Доказательство Теоремы[править | править код]

Пусть и нечётные делители числа . Пусть и , где и удовлетворяют утверждению Леммы, тогда выполнено равенство
,
где . В силу Леммы, целое число удовлетворяет неравенству . Следовательно выполнено первое утверждение Теоремы.

Для доказательства второго утверждения положим , Так как , то и . Используя оценку сверху для , получаем
.
Откуда следует, что . Теорема доказана. [4]

Алгоритм (модифицированный)[править | править код]

Пусть нечётно и .

Шаг 1. Для проверить условие . Если на этом шаге не удалось разложить на множители, то переходим к шагу 2.

Шаг 2. Если на шаге 1 делитель не найден и  — составное, то , где  — простые числа, и . Тогда для всех и всех проверить, является ли число квадратом натурального числа. Если является, то для и выполнено сравнение:

или .

В этом случае для проверяется неравенство . Если оно выполнено, то  — разложение на два множителя.

Если алгоритм не нашёл разложение на два множителя, то  — простое число.[5]

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

Трудоёмкость[править | править код]

Вычисление зависимости от величины факторизуемого числа[править | править код]

На первом шаге нужно произвести операций деления для поиска маленьких делителей числа .

Трудоёмкость второго шага оценивается в операциях тестирования числа , на то, является ли оно полным квадратом. Трудоёмкость второго этапа оценивается сверху величиной

.
Таким образом трудоёмкость всего есть величина . [6]

Зависимость от разрядности факторизуемого числа[править | править код]

В большинстве случаев более важную роль играет зависимость времени исполнения от разрядности исследуемого числа. Имея полиномиальную зависимость для величины получаем экспоненциальную зависимость времени выполнения метода Лемана от разрядности факторизуемого числа. [7]

, где  — разрядность.

Некоторые частные случаи[править | править код]

Как усовершенствование метода Ферма метод Лемана также существенно зависит от расстояния между множителями числа, время его выполнения линейно зависит от дистанции. Однако если расстояние между множителями мало метод Лемана значительно проигрывает методу Ферма.

Для чисел с небольшим простым делителем ситуация обратная — метод Лемана благодаря последовательным делениям на шаге один достаточно быстро выделит простой множитель. [7]

Псевдокод[править | править код]

for to do

if then
return
end if

end for for to do

for to do
if then
if then
return
else if then
return
end if
end if
end for

end for

Пояснения:

означает, что целочисленно делится на .

Функция возвращает , если является полным квадратом и в противном случае.

Функция возвращает наибольший общий делитель чисел и . [7]

Возможности параллельной реализации метода[править | править код]

Общая идея[править | править код]

Параллельная реализация основана на следующем подходе:[7]

Шаг 1:
Каждому вычислительному процессу, участвующему в факторизации, выдаётся свой набор потенциальных делителей из множества . Вычислительный процесс поочерёдно проверяет на делимость на элементы своего набора делителей. Через некоторые промежутки времени главный процесс-координатор «опрашивает» вычислительные процессы на предмет выявления делителя. В случае, когда достаточно проверить на простоту, процесс-координатор, получив информацию о нахождении делителя, посылает остальным процессам сигнал на завершение работы. Если же делитель не найден, или поставлена цель найти все делители, поиск делителей продолжается.


Шаг 2:
Каждому вычислительному процессу аналогично с шагом 1 выдаётся свой набор чисел из множества . Вычислительный процесс поочерёдно проверяет все условия, описанные в алгоритме, определяя, найден ли нетривиальный множитель. Аналогично с шагом 1 процесс-координатор периодически опрашивает процессы на момент нахождения делителя и принимает решение о завершении или не завершении вычислений.


Применение данного подхода позволяет получить линейное ускорение при увеличении количества процессов на машине с распределенной памятью. [7]

Реализация с применением технологии GPGPU[править | править код]

Для успешной реализации алгоритма с применением технологии GPGPU нужно решить две проблемы:[8]
1. Для каждой операции алгоритма решить, стоит ли выполнять её на CPU или на GPU.
2. Определить число используемых ядер GPU.

Описанный выше подход можно использовать для разбиения задачи.[8]

Шаг 1:
Все операции этого шага следует выполнять на GPU.

Пусть  — число доступных ядер GPU,  — число элементов множества . Рассмотрим два случая:
1. : Используем ядер GPU.
2. : Организуем итераций. На каждой итерации выполняем очередные делений на ядрах. В конце каждой итерации определяем, завершить или продолжить исполнение.

Шаг 2:

Распределить между ядрами GPU аналогично шагу 1. На каждом ядре GPU выполнить пункты 1—3:
1. Проверить, является ли число квадратом натурального числа.
2. В случае получения положительного результата в предыдущем пункте, вычислить и .
3. Для значений и проверить условие .
4. Для значений и , прошедших последнюю проверку, проверить выполнение двойного условия .

Последний пункт целесообразно выполнять на CPU, так как вероятность исполнения данных операций мала, а проверка ветвлений на GPU выполняется достаточно медленно.[8]

Пример[править | править код]

Разберём пример с , тогда для , где , проверяем является ли число делителем числа . Нетрудно убедиться, что таких нет, тогда переходим к следующему пункту.

Для всех и всех проверяем, является ли число квадратом натурального числа. В нашем случае существуют такие и , что выражение является полным квадратом и равно . Следовательно и . Тогда , удовлетворяет неравенству и является делителем числа . В итоге, мы разложили число на два множителя: и .

Примечания[править | править код]

  1. 1 2 Lehman, R. Sherman. Factoring Large Integers // Mathematics of Computation. — 1974. — Т. 28, № 126. — С. 637—646. — doi:10.2307/2005940.
  2. 1 2 3 Нестеренко, 2011, p. 140.
  3. 1 2 Василенко, 2003, p. 65—66.
  4. Нестеренко, 2011, p. 142.
  5. Василенко, 2003, p. 65.
  6. 1 2 Нестеренко, 2011, p. 143.
  7. 1 2 3 4 5 Макаренко А.В.,Пыхтеев А. В., Ефимов С. С. Исследование параллельных алгоритмов факторизации целых чисел в вычислительных кластерных системах // Омский государственный университет им. Ф. М. Достоевского (Омск). — 2012. — Т. 4, № 66. — С. 149—158.
  8. 1 2 3 Желтов С. А. Адаптация метода Шермана—Лемана решения задачи факторизации к вычислительной архитектуре CUDA // Российский государственный гуманитарный университет (Москва). — 2012. — Т. 14, № 94. — С. 84—91.

Литература[править | править код]

  1. Василенко О. Н. Теоретико-числовые алгоритмы в криптографии. — М.: МЦНМО, 2003. — 328 с. — ISBN 5-94057-103-4. Архивная копия от 27 января 2007 на Wayback Machine
  2. Алексей Нестеренко. Введение в современную криптографию. — МЦНМО, 2011. — 190 с.
  3. Richard Crandall, Carl Pomerance. A Computational Perspectives. — 2nd. — Springer, 2011. — 597 с. — ISBN 0-387-25282-7.