Эта история началась в далёком 1998 году. По какой-то неведомой сегодня причине, может от скуки, а может быть была какая-то задача, которую я не в силах сегодня вспомнить, но, как бы там ни было, меня заинтересовали закономерности в распределении простых чисел, т. е. таких, которые делятся без остатка только на себя и на единицу. Знакомых математиков у меня не было, а Интернет в то время был совершенно не таким, каким мы знаем его сегодня, поэтому найти в нём ответы на свои вопросы я в то время не смог.

Удивительно, но мне удалось очень быстро найти такие закономерности самостоятельно. Я обнаружил, что если взять ряд всех натуральных чисел, то есть все целые числа от единицы и больше, и разбить его на группы по 30 чисел, а затем расположить эти группы в виде строк таблицы одну под другой, то все простые числа будут расположены в столбцах этой таблицы с определёнными номерами. Исключением из этого правила являются лишь три первых простых числа: 2, 3 и 5, произведение которых между собой как раз равно 30. Другими словами, взяв любое число, можно с уверенностью сказать, может ли это число быть простым, в этом случае оно будет давать один из определённых остатков при делении на 30 — это и будет номер столбца в нашей таблице, или оно простым совершенно точно не является, оно — составное.

Долгое время я пребывал в наивной уверенности, что обладаю тайным знанием, а также в скромных мечтах, что однажды настанет день, когда мне получится поделиться им с человечеством. Конечно, всегда находились более насущные и срочные дела, пока несколько лет назад я не решил взяться за факторизацию. Честно говоря, я был довольно разочарован, когда я узнал, что моё открытие, оказывается, давно известно математикам. Как же я был наивен тогда! То, что я обнаружил тогда по наитию, легко объяснимо — любое простое число, большее 5, по определению не может делиться ни на 2, ни на 3, ни на 5. Следовательно, оно является взаимно простым с 30. Количество натуральных взаимно простых чисел с заданным числом , меньших или равных ему, равно значению функции Эйлера для этого числа: . Число 30 имеет взаимно простых с ним чисел. Это означает, что все простые числа больше 5 будут давать один из следующих остатков при делении на 30:

Это и есть номера столбцов в нашей таблице, содержащих все простые числа больше 5.

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

Самым элементарным и наивным алгоритмом является простой перебор чисел в попытках найти число, которое будет делить заданное число без остатка. Если для небольших чисел мы с лёгкостью можем найти все его сомножители (или делители — кому как нравится) в уме, то чем большее число мы берём, тем эта операция становится сложнее. В итоге она становится сложной настолько, что требуются сотни, тысячи, а может и миллионы лет, в зависимости от размерности числа, чтобы найти его разложение на сомножители на современных компьютерах. Именно на этой сложности, а вернее на том, что мы не знаем быстрого способа раскладывать большие числа на сомножители, основываются некоторые криптографические алгоритмы, например RSA.

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

Я подумал, что если взять два числа из нашей таблицы остатков деления на 30, то их произведение будет иметь строго определённый остаток от деления на 30, а зная этот остаток, мы можем узнать, каким столбцам могут принадлежать исходные сомножители. Таким образом, у нас появляется дополнительная информация о исходных числах, произведение которых нам нужно факторизовать!

Давайте, наконец, введём стандартную формулу, связывающую искомые сомножители и их произведение. Вот её обычный вид:

где - факторизуемое число.

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

То есть, произведение остатков по модулю 30 (остатков от деления чисел и на 30) соответствует остатку от деления произведения и на 30.

Hidden text

Пусть

Тогда:

Если взять любые другие , , такие что:

то:

Если вам, как и мне, более понятны словесные описания, то из всего этого следует, что мы можем выразить разность между двумя произвольными числами и как сумму числа полных строк между ними в нашей таблице остатков по модулю 30 — , умноженного на количество чисел в строке — 30, и абсолютного значения разности между номерами столбцов, в которых находятся и — . На языке математики это записывается так:

где

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

Hidden text

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

1. Перемножал эти два числа и вычислял остаток от деления на 30

2. Вычислял разность:

3. Группировал полученные по соответствующему значению .

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

Дополнительно я применил два метода фильтрации:

• Исключил значения , которые никогда не приводят к полному квадрату при вычислении (подробнее см. далее);

• Убрал такие дельты, которые дают одинаковые значения при вычислениях.

Это позволило сократить число возможных дельт для каждого , то есть сократить максимальное теоретическое число операций при факторизации .

Ключевая формула метода

Для факторизации заданного числа мы должны найти такое значение , при котором является полным квадратом (квадратным числом):

Если мы найдём такое целочисленное значение , то сомножители находятся сразу по формулам:

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

Как работает алгоритм?

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

Т.е. не может превышать наше начальное число , разделенное на 30 с округлением вниз до ближайшего целого. Мы можем перебирать абсолютные значения от 0 до максимально возможного — в этом случае мы сначала проверяем близкие по значению кандидаты в сомножители, постепенно увеличивая разницу между ними, или наоборот — от максимально возможного до 0, изначально проверяя максимально удалённые друг от друга кандидаты, или использовать какую-нибудь комбинированную стратегию. Следует учитывать, что может принимать и отрицательные значения, поскольку мы не знаем заранее какое из чисел и является бо́льшим.

Пример 1:

Допустим, нам нужно факторизовать:

1. 

2. Таблица даёт:

3. Пробуем , перебираем

4. При :

5. Множители:

Мы нашли простые сомножители за 19 итераций. Если бы мы использовали метод Ферма, то смогли бы обнаружить эти сомножители всего за 10 итераций. В данном случае наш метод проигрывает методу Ферма из-за того, что и различаются незначительно, поскольку метод Ферма наиболее эффективен именно когда сомножители числа примерно равны между собой.

Попробуем пример с большей абсолютной разницей между и .

Пример 2:

Аналогично:

1. 

2. Допустимые дельты:

3. При и :

4. Получаем:

Мы нашли сомножители за 301 итерацию. Алгоритму Ферма потребовалось бы 715 итераций для поиска сомножителей.

Hidden text

При использовании метода Ферма мы бы начали и закончили значениями:

Что даёт итераций.

Пример 3: отрицательное n

1. 

2. Допустимые дельты:

3. При и :

4. Получаем:

Таблица допустимых дельт (фрагмент)

(Полную таблицу см. в препринте)

Сложность алгоритма

Если — число допустимых дельт (обычно 2–4), то:

где поправочный коэффициент 2 введён из-за того, что мы должны перебирать как положительные, так и отрицательные .

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

Заключение

Метод решета дельт получился неожиданно простым и в то же время быстрым. Конечно, при работе с очень большими числами он не сравнится с более продвинутыми методами, такими как метод квадратичного решета или общий метод решета числового поля, но при этом он гораздо, нет, не так — он гораздо проще для понимания и реализации. При этом он остаётся достаточно эффективным при работе с числами, состоящими из десятков цифр.

Что мне особенно хочется отметить:

• он не зависит от размерности , только от разности ;

• его можно легко распараллелить, скорость расчётов при этом растёт линейно (с поправкой на производительность узлов кластера);

• можно использовать различные стратегии подбора , что делает его особенно гибким.

Если вы увлекаетесь криптографией, алгоритмами или просто любите математику, а также умеете писать программы — попробуйте реализовать его сами на своем любимом ЯП. Я сделал это на C++, Python и Matlab. А если у вас под рукой есть вычислительный кластер... вдруг получится факторизовать что-то большое? Например, замахнуться на поиск решений RSA-чисел, многие из которых не найдены до сих пор. Если у вас это получится сделать с помощью метода решета дельт, обязательно дайте мне знать, мне будет очень приятно!

Полный препринт на OSF

? Комментарии c критикой и идеями по оптимизации — горячо приветствуются!