ooptimum May 20 at 08:10

Решето дельт — простой способ раскладывать числа на множители, о котором вам не рассказывали

Medium

10 min

6.8K

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

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

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

$\mathcal{R}_{30} = \{1, 7, 11, 13, 17, 19, 23, 29\}$

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

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

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

Задача со звёздочкой

Пусть у нас есть 64-битное целое беззнаковое число с начальным значением 0, для скорости обработки хранящееся в регистре общего назначения 64-битного процессора. Будем увеличивать значение в этом регистре на единицу в каждой итерации цикла, не делая больше ничего, пока оно не достигнет максимально возможной величины (все биты равны 1). Какое время будет выполняться эта задача на современном процессоре с частотой 3 ГГц?

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

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

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

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

$N = p \cdot q,$

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

Hidden text

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

Т.е. если мы возьмем любые и из, например, первого и седьмого столбца, то их произведение всегда будет в седьмом столбце ( $N \equiv 7 \pmod{30}$ ), как и для и из одиннадцатого и семнадцатого столбцов. Это следует из того, что для любых
$x := p \bmod 30$ и $y := q \bmod 30$ верно, что

$x \cdot y \equiv p \cdot q \pmod{30}$

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

Hidden text

Пусть

$x \equiv 7 \pmod{30}, \quad y \equiv 11 \pmod{30}$

Тогда:

$x \cdot y \equiv 7 \cdot 11 \equiv 17 \pmod{30}$

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

$x' = 7 + 30k, \quad y' = 11 + 30m, \quad \text{где } k, m \in \mathbb{Z}$

то:

$x' \cdot y' \equiv 7 \cdot 11 \equiv 17 \pmod{30}$

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

$D = p - q = 30n + \delta, \quad \text{где } n \in \mathbb{Z},\ \delta \in \Delta_v$

где

$\delta \equiv |p - q| \pmod{30}$

Это позволяет нам вычислить все возможные значения $\delta$ для каждого $v \equiv N \pmod{30}$ и занести их в таблицу дельт $\Delta_v$ , которую мы будем использовать в дальнейшем.

Hidden text

Чтобы построить эту таблицу, я перебрал все возможные пары чисел из $\mathcal{R}_{30}$ , назовем числа каждой пары: и , где $a \le b$ . Для каждой пары я:

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

$v = a \cdot b \bmod{30}$

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

$\delta=b-a$

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

Таким образом, для каждого возможного остатка $v \in [0, 29]$ получался список дельт, которые реально возникают при перемножении.

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

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

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

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

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

$m = \sqrt{D^2 + 4N} \in \mathbb{Z},$

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

$p = \frac{m+D}{2}, \quad q = \frac{|m-D|}{2}.$

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

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

Сначала мы должны взять из таблицы все подходящие значения $\delta$ для $v = N \bmod 30$ — мы будем подставлять их в формулу $(30n + \delta)^2 + 4N$ и проверять, не получился ли в итоге полный квадрат. Если получился, то мы можем остановить алгоритм и найти значения сомножителей и . Однако алгоритм является универсальным и может быть применён к составным числам, число простых сомножителей которых больше двух. Поэтому, если мы не знаем наверняка, что число является полупростым (произведением двух простых сомножителей), мы можем продолжить поиск всех сомножителей, пока не переберем все подходящие и $\delta$ . При этом абслютная величина ограничена сверху:

$|n| \le \left\lfloor \frac{N}{30} \right\rfloor.$

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

Больше об отрицательных n

Хотя операция умножения коммутативна ( ${p}\cdot{q}={q}\cdot{p}$ ), данный метод основан на разности D=p−q , величина которой зависит от порядка членов. Чтобы учесть все возможные случаи, мы допускаем отрицательные значения , что позволяет находить решение вне зависимости от того, какой из сомножителей, или больше.

Пример 1:

Допустим, нам нужно факторизовать: $N = 13315381 = 3929 \times 3389$

$N \bmod 30 = 1$
Таблица даёт: $\delta \in \{0, 6\}$
Пробуем $\delta = 0$ , перебираем $n = 0, 1, 2, \dots$
При :

$D = 30 \cdot 18 + 0 = 540$ $m^2 = 540^2 + 4 \cdot 13315381 = 53553124 = 7318^2$

Множители:

$p = \frac{7318 + 540}{2} = 3929, \\q = \frac{7318 - 540}{2} = 3389$

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

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

Пример 2:

N=190223063

Аналогично:

$N \bmod 30 = 23$
Допустимые дельты: $\{2, 22\}$
При и $\delta = 2$ :

$D={30}\cdot{300}+2=9002$ $m^2 = 9002^2 + 4 \cdot 190223063 = 841928256 = 29016^2$

Получаем:

$p = \frac{29016 + 9002}{2} = 19009, \\q = \frac{29016 - 9002}{2} = 10007$

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

Hidden text

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

$a_0=\lceil\sqrt{190223063}\rceil=13793,\quad \\a=\frac{p+q}{2}=\frac{10007+19009}{2}=14508$

Что даёт 14508 - 13793 = 715 итераций.

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

$N = 1936007 = 2341 \times 827$

$N \bmod 30 = 17$
Допустимые дельты: $\{4, 16\}$
При и $\delta = 16$ :

$D={30}\cdot{-51}+16=-1514$ $m^2 = (-1514)^2+4 \cdot 1936007 = 10036224 = 3168^2$

Получаем:

$p = \frac{-1514 + 3168}{2} = 827, \\q = \frac{|-1514 - 3168|}{2} = 2341$

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

$N \bmod 30$	$\delta$
0	0, 1, ..., 14
1	0, 6
2	1, 4, 11, 14
23	2, 22
29	8, 10, 28

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

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

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

$O\left( \frac{2k \sqrt{N}}{30} \right) = O\left( \frac{k \sqrt{N}}{15} \right),$

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

В худшем случае (при k = 15 ) данный метод имеет сложность $O(\sqrt{N})$ , что совпадает со сложностью метода Ферма. Однако, из-за того, что в среднем $k \approx 3$ количество необходимых проверок уменьшается в $30 / (2k) \approx 5$ раз, делая данный метод существенно быстрее для сравнимых значений $|p - q| \gg 0$ .

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

В комментариях к статье мне пишут, что в данных формулах есть ошибки и просят математическое доказательство, что метод решета дельт обязательно найдет решение, если оно существует, не более чем за $\sqrt{N}$ шагов. Строгого доказательства у меня пока нет. Если кто-то поможет его разработать или исправить ошибки в оценке сложности, я буду очень благодарен.

Пока же я подготовил практическое сравнение метода решета дельт с методом Ферма, которое вы можете посмотреть под спойлером.

Практическое сравнение метода решета дельт с методом Ферма

В приведённой ниже таблице произведена оценка количества необходимых шагов для поиска решения для 50 случайно выбранных пар простых и . Номер шага, на котором было найдено решение, находится в столбце step для метода решета дельт и в столбце Fermat для метода Ферма, соответственно. В столбце $<\sqrt{N}$ находится логическое значение, является ли количество шагов step меньше чем $\sqrt{N}$ . Правый столбец - отношение $\frac{step}{Fermat}$ в процентах.

Особо дотошные могут заметить, что step может быть меньше чем и сказать, что это невозможно. На самом деле это результат ещё одной оптимизации метода решета дельт, помимо оптимизаций таблицы дельт, описанных в препринте, при которой я отбрасываю те , которые никогда не могут дать полный квадрат в D^2 + 4N - мы можем вычислить это заранее, во время подготовки рабочих данных для работы алгоритма, и не использовать такие во время проверок, что заметно снижает количество вычислений. Время этой подготовки пренебрежимо мало по сравнению с временем поиском решений. Я не знаю как описать данную оптимизацию математически, поэтому ни в препринте, ни в статье она пока не описана. Однако она будет присутствовать в демонстрационном коде, который я готовлю к публикации на GitHub. Если кто-то поможет описать её языком математики, я также буду очень благодарен.

p	q	N	n	δ	step	Fermat	<√N
19391	53231	1032202321	1128	0	843	4183	✅	20,15%
79349	23099	1832882551	1875	0	1405	8411	✅	16,70%
26723	75577	2019644171	-1629	16	2448	6209	✅	39,43%
22721	48371	1099037491	855	0	638	2394	✅	26,65%
27239	11597	315890683	521	12	259	1644	✅	15,75%
100183	11681	1170237623	2950	2	2946	21723	✅	13,56%
61613	63629	3920373577	67	6	33	8	✅	412,50%
39709	35141	1395413969	152	8	219	69	✅	317,39%
74177	77951	5782171327	-126	6	64	23	✅	278,26%
36721	52747	1936922587	534	6	266	723	✅	36,79%
60331	26993	1628514683	-1112	22	1119	3307	✅	33,84%
51413	36923	1898322199	483	0	361	598	✅	60,37%
63281	57839	3660109759	-182	18	142	61	✅	232,79%
56377	71411	4025937947	501	4	497	443	✅	112,19%
88007	36073	3174676511	1731	4	2594	5695	✅	45,55%
10459	90437	945880583	-2666	2	2663	19692	✅	13,52%
76387	42709	3262412383	-1123	12	566	2430	✅	23,29%
22541	90191	2032995331	2255	0	1684	11277	✅	14,93%
86257	22859	1971748763	-2114	22	2126	10153	✅	20,94%
66179	89303	5909983237	-771	6	389	864	✅	45,02%
83339	44987	3749171593	1278	12	636	2932	✅	21,69%
58237	53047	3089298139	173	0	124	60	✅	206,67%
82619	62299	5147081081	677	10	1018	715	✅	142,38%
87803	23599	2072062997	2140	4	2132	10181	✅	20,94%
36671	89983	3299766593	1777	2	1777	5883	✅	30,21%
97387	31177	3036234499	2207	0	1648	9179	✅	17,95%
17029	56737	966174373	-1324	12	664	5799	✅	11,45%
29873	17539	523942547	411	4	404	816	✅	49,51%
20543	67153	1379524079	-1554	10	2341	6706	✅	34,91%
91639	30211	2768505829	2047	18	1532	8308	✅	18,44%
63761	28081	1790472641	1189	10	1786	3607	✅	49,51%
18701	92581	1731357281	-2463	10	3688	14031	✅	26,28%
93901	63317	5945529617	-1020	16	1024	1501	✅	68,22%
95713	60509	5791497917	-1174	16	1182	2009	✅	58,84%
22777	15107	344092139	-256	10	397	392	✅	101,28%
42649	56453	2407663997	460	4	452	483	✅	93,58%
84691	56333	4770898103	-946	22	958	1440	✅	66,53%
95261	26891	2561663551	2279	0	1706	10463	✅	16,31%
63487	90359	5736621833	895	22	892	1182	✅	75,47%
50767	95111	4828500137	1478	4	1474	3451	✅	42,71%
59561	71363	4250451643	393	12	195	266	✅	73,31%
42013	36583	1536961579	181	0	134	93	✅	144,09%
58129	93263	5421284927	1171	4	1170	2066	✅	56,63%
61121	21341	1304383261	1326	0	988	5114	✅	19,32%
52511	84319	4427675009	1060	8	1586	1874	✅	84,63%
95177	71633	6817814041	-785	6	597	834	✅	71,58%
22283	57193	1274431619	-1164	10	1744	4038	✅	43,19%
42157	11597	488894729	-1019	10	1527	4766	✅	32,04%
78017	43961	3429705337	1135	6	564	2425	✅	23,26%
29531	55259	1631853529	857	18	643	1998	✅	32,18%

Заключение

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

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

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

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

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

Hidden text

Препринт опубликован на osf.io, т.к. я не являюсь математиком, не вхожу в академическую среду и у меня нет endorsement на arXiv.

📦 Исходный код реализации метода доступен на GitHub: github.com/ooptimum/delta-sifter

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

Hubs: