- Метод Лемана
-
Алгоритм Лемана (или алгоритм Шермана Лемана) детерминировано раскладывает данное натуральное число на множители за арифметических операций. Алгоритм был впервые предложен американским математиком Шерманом Леманом в 1974 году.[1]. Данный алгоритм был первым детерминированным алгоритмом факторизации целых чисел чисел, имеющим оценку меньшую, чем . В настоящий момент носит чисто исторический интерес и, как правило, не используется на практике.[2]
Содержание
Алгоритм
Пусть нечетно и .
Шаг 1. Для проверить условие . Если на этом шаге мы не разложили на множители, то переходим к шагу 2.
Шаг 2. Если на шаге 1 делитель не найден и — составное, то , где — простые числа, и . Тогда для всех и всех проверить, является ли число квадратом натурального числа. Если является, то для и выполнено сравнение:
- или .
В этом случае для проверяется неравенство . Если оно выполнено, то — разложение на два множителя.
Если алгоритм не нашел разложение на два множителя, то — простое число.[3]
Данный алгоритм в начале проверяет имеет ли простые делители не превосходящие , а после устраивает перебор значений и для проверки выполнимости указанной ниже Теоремы. В случае, если искомые значения и , не найдены, то мы получаем что число простое. Таким образом мы можем рассматривать данный алгоритм как тест числа на простоту[4]
Доказательство
Метод Лемана развивает идеи, заложенные в алгоритме Ферма и ищет делители числа , используя равенство для некоторого целого числа . Он основан на следующей теореме.
Теорема: Пусть составное число, являющееся произведением двух нечетных взаимно простых чисел, удовлетворяющих неравенствам . Тогда, найдутся натуральные числа и такие, что
- 1. Выполнено равенство при ,
2. Выполнено неравенство .
Для доказательства данной теоремы нам потребуется следующая Лемма.[2]
Лемма: Пусть выполнены условия Теоремы. Тогда найдутся натуральные числа такие что и .
Доказательство Леммы: Если , т.е. , то утверждение теоремы выполнено для . Далее будем считать .
Разложим в непрерывную дробь. Мы обозначаем -ю подходящую дробь к . Тогда, , ,
поскольку . Выберем первый номер такой, что
, .
Такой номер обязательно найдется, поскольку у последней подходящей дроби знаменатель . Докажем, что и удовлетворяют утверждению леммы. Очевидно, что . Далее,
по свойствам подходящих дробей.
Рассмотрим сначала случай . В этом случае,
что и требовалось доказать.Теперь рассмотрим случай . Тогда перевернем неравенства , откуда . Следовательно, по свойствам непрерывных дробей, выполнены неравенства
. Отсюда
Лемма доказана.[5]Доказательство Теоремы: Пусть и нечетные делители числа . Пусть и , где и удовлетворяют утверждению Леммы, тогда выполнено равенство
,
где . В силу Леммы, целое число удовлетворяет неравенству . Следовательно выполнено первое утверждение Теоремы.
Для доказательства второго утверждения положим , Так как , то и . Используя оценку сверху для , получаем
.
Откуда следует, что . Теорема доказана. [6]Трудоемкость
На первом шаге нам требуется произвести операций деления для поиска маленьких делителей числа .
Трудоемкость второго шага оценивается в операциях тестирования числа , на то, является ли оно полным квадратом. В начале заметим, что для всех выполняется только две проверки: и . Тогда, трудоемкость второго этапа оценивается сверху величиной
.
Таким образом трудоемкость всего есть величина . [4]Пример
Разберем пример с , тогда для , где , проверяем является ли число делителем числа . Не трудно убедится, что таких нет, тогда переходим к следующему пункту.
Для всех и всех проверяем, является ли число квадратом натурального числа. В нашем случае существуют такие и , что выражение является полным квадратом и равно . Следовательно и . Тогда , удовлетворяет неравенству и является делителем числа . В итоге, мы разложили число на два множителя: и .
Примечания
- ↑ Lehman, R. Sherman Factoring Large Integers // Mathematics of Computation. — 1974. — Т. 28. — № 126. — С. 637-646. — DOI:10.2307/2005940
- ↑ 1 2 Нестеренко, 2011, p. 140
- ↑ Василенко, 2003, p. 65
- ↑ 1 2 Нестеренко, 2011, p. 143
- ↑ Василенко, 2003, p. 65-66
- ↑ Нестеренко, 2011, p. 142
Для улучшения этой статьи желательно?: - Проставить интервики в рамках проекта Интервики.
- Найти и оформить в виде сносок ссылки на авторитетные источники, подтверждающие написанное.
Литература
- Василенко О. Н. Теоретико-числовые алгоритмы в криптографии. — М.: МЦНМО, 2003. — 328 с. — ISBN 5-94057-103-4
- Алексей Нестеренко. Введение в современную криптографию. — МЦНМО, 2011. — 190 с.
- Richard Crandall, Carl Pomerance A Computational Perspectives. — 2nd. — Springer, 2011. — 597 с. — ISBN 0-387-25282-7
Категория:- Алгоритмы факторизации
Wikimedia Foundation. 2010.