Факторизация чисел и методы решета, часть I

В работе рассматривается традиционный подход, который автором в ряде статей критикуется. Здесь я воздержусь от критики, и направлю свои усилия на разъяснение сложных моментов в традиционном подходе. Весь арсенал существующих методов не решает задачу факторизации в принципе, так как почти все решеточные и другие алгоритмы построены на жесткой связи и зависимости времени их выполнения от разрядности факторизуемого числа N. Но замечу, что у чисел имеются и другие свойства кроме разрядности, которые можно использовать в алгоритмах факторизации. Оценки сложности — эвристические опираются на рассуждения ограниченные авторским пониманием проблемы. Пора бы уже понять, что факторизация чисел в глубоком тупике, а математикам (не только им) пересмотреть свое отношение к проблеме и создать новые модели. Простая идея факторизации целого нечетного числа N исторически — состоит в поиске пары квадратов чисел разной четности, разность которых кратна kN, при k =1 разложение успешно реализуется так как в этом случае сразу получаем произведение двух скобок c сомножителями N. При k>1 случаются тривиальные разложения. Таким образом, проблема факторизации преобразуется в проблему поиска подходящих квадратов чисел. Понимали эти факты многие математики, но П. Ферма первым в 1643 году реализовал идею поиска таких квадратов в алгоритме, названном его именем. Перепишем иначе приведенное соотношение . Если разность слева от равенства не равна квадрату, то изменяя х, можно подобрать другой квадрат, чтобы и справа получался квадрат. Практически все нынешние алгоритмы используют эту идею (поиска пары квадратов), но судя по результатам, похоже, что идея себя исчерпала. Читать дальше →

Источник: Хабрахабр