Методы факторизации натуральных чисел. Ишмухаметов Ш.Т. - 51 стр.

Глава 2. Простые алгоритмы факторизации                                        52

2. Простые алгоритмы факторизации
       Факторизацией       целого      числа   называется   его   разложение    в
произведение простых сомножителей. Такое разложение, согласно основной
теореме арифметики, всегда существует и является единственным (с
точностью до порядка следования множителей). Все методы факторизации
в зависимости от их производительности можно разбить на две группы:
экспоненциальные методы и субэкспоненциальные методы. Все эти методы
достаточно трудоемки, поэтому требуют значительных вычислительных
ресурсов для чисел большой длины. Однако теоретическое обоснование
необходимой    сложности       таких    вычислений   или,   другими    словами,
существование высоких нижних оценок не доказано, поэтому вопрос о
существовании алгоритма факторизации с полиномиальной сложностью на
классическом компьютере для выполнения факторизации является одной
из важных открытых проблем современной теории чисел. В то же время
факторизация с полиномиальной сложностью возможна на квантовом
компьютере с помощью алгоритма Шора.
      В этой главе мы дадим описание наиболее известных алгоритмов
факторизации, имеющих экспоненциальную оценку сходимости.


2.1. Метод Ферма
     Пусть n = p · q – известное целое число, являющееся произведением
двух неизвестных простых чисел p и q , которые требуется найти.
Большинство современных методов факторизации основано на идее,
предложенной еще Пьером Ферма, заключающейся в поиске пар натуральных
чисел A и B таких, что выполняется соотношение:

              n = A2 − B 2 .                                              (2.20)

      Алгоритм Ферма может быть описан следующим образом:

      1. Вычислим целую часть от квадратного корня из n:
                   √
              m = d ne.