5.6 Факторизация чисел

Алгоритм нахождения периода функции, рассмотренный выше, может быть с успехом применен для разложения заданного целого числа на множители. Эта задача решается с помощью алгоритма, придуманного П. Шором в 1994 г.

В настоящее время алгоритм Шора- самый знаменитый из известных квантовых алгоритмов. Он позволяет за шагов осуществить разложение целого числа на множители и, таким образом, является алгоритмом полиномиальной сложности. Заметим, что аналогичный классический полиномиальный алгоритм неизвестен.

Пусть - целое нечетное число (при четном имеем тривиальное решение задачи). Нам требуется разложить данное число на простые множители или показать, что оно простое.

Выберем случайно число . Вычислим наибольший общий делитель (НОД) чисел и (это можно сделать с помощью алгоритма Евклида, который изложен в конце настоящего раздела).

Если НОД чисел и оказался большим, чем единица, то задача решена.

Предположим, что НОД чисел и равен единице. Тогда, согласно известной в теории чисел теореме Эйлера, существует такое , что:

Выберем минимальное , удовлетворяющее указанному тождеству. Оно называется порядком числа по модулю .

Рассмотрим теперь функцию

Заметим, что утверждение о том, что есть порядок числа по модулю и утверждение о том, что функция периодична с периодом , эквивалентны.

Таким образом, задача о вычислении порядка сводится к задаче о нахождения периода функции (для чего можно применить алгоритм раздела 5.5).

Сделаем одно замечание. Чтобы применить алгоритм из разд. 5.5., следует ограничить область определения функции некоторым конечным интервалом . Алгоритм из раздела 5.5 предполагает, что делится на без остатка. Заметим, что это предположение несущественно, если только выбрать достаточно большим так, чтобы на нем укладывалось большое число периодов функции .

Предположим, что найденное - четное, тогда (1) можно переписать в виде:

Это означает, что число должно делиться на без остатка.

Предположим дополнительно, что каждое из чисел не делится на без остатка. Тогда у каждого из этих чисел есть общие делители с числом .

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

Мы видим, что изложенный метод срабатывает не всегда. Чтобы метод сработал, нам нужно, чтобы было четным и, одновременно, числа не делились на без остатка. Можно показать, что это происходит с вероятностью , если только выбирается случайно. Такой вероятности достаточно, чтобы путем повторения добиться гарантированно успеха.

Приведем пример. Пусть ,

Прямым вычислением получаем (по модулю 85): , , , , , , , , , , , , , , , , и т.д. Таким образом

Далее:

Вычислим теперь необходимые наибольшие общие делители. НОД(5764800, 85)=5, НОД(5764802, 85)=17.

Окончательно имеем разложение 17*5=85.

В рассмотренном демонстративном примере мы нашли посредством прямого расчета. В реальных задачах с большим для этого может потребоваться квантовый компьютер.

Для справок приводим алгоритм Евклида нахождения наибольшего общего делителя.

Пусть и - натуральные числа. Без ограничения общности будем считать, что .

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

Пример: Найдем наибольший общий делитель чисел 315 и 168. Алгоритм Евклида приведет нас к последовательности пар чисел: [315;168] [168;147] [147; 21] [21;0]. Число 21 и есть наибольший общий делитель чисел 315 и 168 : НОД(315, 168)=21

Резюмируем полученный результат. Мы описали полиномиальный квантовый алгоритм разложения целого числа на множители. Примечательно, что подобный классический алгоритм неизвестен. Рассматриваемый результат имеет важное теоретическое и практическое значение.

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

Отмеченная алгоритмическая неполнота классической арифметики лежит в основе современных криптографических методов защиты информации, которые нашли широкое применение в банковской сфере, Интернете и др. Речь, в частности, идет о так называемом коде RSA, который, как раз основан на сложности задачи разложения большого целого числа на множители. Как следует из представленных выше результатов, создание квантовых компьютеров сделает классические криптографические системы беззащитными. Таким образом, встает вопрос о разработке новых (квантовых) способов защиты информации. Этому вопросу посвящен следующий раздел.