Алгоритм Лемана (или алгоритм Шермана Лемана) детерминировано раскладывает данное натуральное число на множители за арифметических операций. Алгоритм был впервые предложен американским математиком Шерманом Леманом в 1974 году[1]. Данный алгоритм был первым детерминированным алгоритмом факторизации целых чисел, имеющим оценку меньшую, чем . В настоящий момент носит чисто исторический интерес и, как правило, не используется на практике.[2]
Метод Лемана развивает идеи, заложенные в методе факторизации Ферма, и ищет делители числа , используя равенство для некоторого целого числа . Он основан на следующей теореме.[2]
Предположим, что — положительное нечетное целое, а — целое такое, что . Если , где и простые и
тогда существуют такие неотрицательные целые числа , и , что
и
Если — простое, таких чисел , и не существует.
Пусть
составное число, являющееся произведением двух нечётных взаимно простых чисел, удовлетворяющих неравенствам
. Тогда, найдутся натуральные числа
и
такие, что
Пусть выполнены условия Теоремы. Тогда найдутся натуральные числа такие что и .[3]
Если , то есть , то утверждение теоремы выполнено для . Далее будем считать .
Разложим в непрерывную дробь. Мы обозначаем -ю подходящую дробь к . Тогда
, , ,
поскольку . Выберем первый номер такой, что
, .
Такой номер обязательно найдётся, поскольку у последней подходящей дроби знаменатель . Докажем, что и удовлетворяют утверждению леммы. Очевидно, что . Далее,
по свойствам подходящих дробей.
Рассмотрим сначала случай . В этом случае
,
что и требовалось доказать.
Теперь рассмотрим случай . Тогда перевернём неравенства , откуда . Следовательно, по свойствам непрерывных дробей, выполнены неравенства
. Отсюда
Лемма доказана.[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:
Для успешной реализации алгоритма с применением технологии GPGPU нужно решить две проблемы:[8]
Разберём пример с , тогда для , где , проверяем является ли число делителем числа . Не трудно убедится, что таких нет, тогда переходим к следующему пункту.
Для всех и всех проверяем, является ли число квадратом натурального числа. В нашем случае существуют такие и , что выражение является полным квадратом и равно . Следовательно и . Тогда , удовлетворяет неравенству и является делителем числа . В итоге, мы разложили число на два множителя: и .
Для улучшения этой статьи желательно: |
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .