Dec 19 2021 at 23:01

Факторизация Целых Чисел

Translation

Invite pending

Цель статьи

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

Почему это важно?

В современной криптографии активно используется алгоритм шифрования RSA. RSA сам по себе не является практически надежным (semantically secured), так как при одних и тех же значениях входных параметров (ключа и сообщения) выдаёт одинаковый результат. Однако, его удобно использовать как вспомогательный алгоритм, для шфровки, например, сеансового ключа (используется в TLS, а так же в ранних версиях PGP). Несложно показать, что задача дешифровки сообщения или ключа, зашифрованного с помощью RSA сводится к проблеме факторизации целых чисел.

Disclaimer

Есть отличная статья Connelly Barnes "Integer Factorization Algorithms". Эта статья является не прямым переводом той, с некоторыми дополнениями и исключая код и доказательства.

Матчасть

Немножко сведений из институсткого курса по математике для более глубокого понимания задачи:

Основная теорема арифметики

Любое натуральное число больше единицы можно разложить в виде произведения k простых чисел. Например $21 = 3\cdot 7$ . Теперь рассмотрим число

(Warning) Огромное число

N = 25195908475657893494027183240048398571429282126204032027777137836043662020707595556264018525880784406918290641249515082189298559149176184502808489120072844992687392807287776735971418347270261896375014971824691165077613379859095700097330459748808428401797429100642458691817195118746121515172654632282216869987549182422433637259085141865462043576798423387184774447920739934236584823824281198163815010674810451660377306056201619676256133844143603833904414952634432190114657544454178424020924616515723350778707749817125772467962926386356373289912154831438167899885040445364023527381951378636564391212010397122822120720357

Это число известно как RSA-2048. В Марте 1991 года RSA Laboratories предлжили приз в 200,000$ тому что сможет его факторизовать. На данный момент его не факторизовали. Для сравнения: последнее факторизованное число из RSA Factoring Challange - RSA-250:

(Warning) Еще одно огромное число

N = 2140324650240744961264423072839333563008614715144755017797754920881418023447140136643345519095804679610992851872470914587687396261921557363047454770520805119056493106687691590019759405693457452230589325976697471681738069364894699871578494975937497937

Оно имеет на 367 цифр в записи меньше чем RSA-2048. Его разложили с помощью Number Field Sieve algorithm (GNFS) задействовав 2700 CPU ядер-лет используя 2.1GHz Intel Xeon Gold 6130 CPU.

Вспомогательная теорема

Пусть у числ есть два натуральных делителя: $p, s:p\le s$ .Тогда младший из них $p \le \sqrt{N}$ .

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

Если $p>\sqrt{N}$ , то $s \ge p > \sqrt{N}$ . Тогда $N = p\cdot s > \sqrt{N} \cdot \sqrt{N} = N$ , то есть N > N , а это не возможно.

Открытая проблема математики

На данный момент в теории сложности вычеслений стоит открытый вопрос: "Принождежит ли факторизация целых чисел классу сложности P?". В более простых терминах: Можно ли найти делитель числа N меньше чем любое на перед заданное число за количество шагов O(P(n)) , где - количество цифр , P(n) - многочлен о. Другими словами, ответ на вопрос: "Какой самый быстрый алгоритм факторизации?" еще не найден.

Алгоритмы факторизации чисел

Мы будем рассматривать следующие алгоритмы:

Перебор делителей (Trial Division)
Метод Ферма (Fermat Factorization)
ро-алгоритм Полларда (Pollard rho Factorization)
Метод Брента (Brent's Factorization Method)
p-1 алгоритм факторизации Полларда (Pollard p-1 Factorization)

Нужно отметить, что все эти алгоритмы ставят себе целью не разложить число на все простые множители, а только найти числа p, s: N=ps , так как если мы смогли это сделать, можем сделать то же самое для и , что является более простой задачей.

Перебор Делителей

Перебор делителей - простейший алгоритм факторизации. Будем смотреть является ли числ N/s натуральным для всех s начиная с 2 и до $\sqrt{N}$ .

Сложность этого алгоритма - $O(\sqrt{N}\log^2{N})$ или $O(\sqrt{N}\log{N})$ в зависимости от того, гоняем ли мы алгоритм по всем числам или только по простым.

Метод Ферма

Метод был предложен в 1600 году. Он основывается на формуле x^2 - y^2 = (x + y)(x - y) . Тогда вместо чисел $p, s: N = p\cdot s, s \le p$ мы ищем числа x, y: x^2 = N + y^2 . Числа x и y обязательно целые, так как сумма и разность нечетных чисел - четное число, а $x = \frac{p + s}{2}$ и $y = \frac{p - s}{2}$ (если p или s четные, то сразу можем решить задачу: s = 2).

К тому же, $x = \sqrt{N + y^2} \ge \sqrt{N}$ и $x = \frac{p + s}{2} \le \frac{2p}{2} = p \le N$ , а следовательно $\sqrt{N} \le x \le N$ . Тогда алгоритм выглядит так: Последовательно проверяем, является ли число x^2 - N квадратом целого числа для всех x от $\sqrt{N}$ до .

Сложность алгоритма в худшем случае O(N) . У этого алгоритма есть ряд улучшений - оптимизация методом перебора делителей, метод решета, Крайчика-Ферма и др.

Ро-алгоритм Полларда

Теперь подходим к более менее современным алгоритмам: Ро-алгоритм Полларда был предложен в 1975 году. Он основан на следующей последовательности:

$x_0 \equiv 2 \; mod\; N$

$x_{n+1} \equiv x_n^2 + 1 \; mod\; N$

Видно, что последовательность переодична и период $Period \le N$ , так как все берется по модулю N. Можно показать, что если мы найдем $i, j: i\ne j, x_i \equiv x_j \;(mod\; s), x_i \not\equiv x_j \;(mod\; N)$ , то gcd(x_i-x_j, N) - делитель N. gcd - наибольший общий делитель.

Причем это справедливо для любой последовательности с модулем N. В статье Weisstein, Eric W. "Pollard Rho Factorization." показано, что ожидаемый период пропорционален $\sqrt{N}$ почти для всех N. Это одна из причин использования именно такой.

Есть также другие варианты задания последовательности: например $x_{n+1} \equiv x_n^2 - x_n + 1 \; mod\; N$ или $x_{n+1} \equiv x_n^2 + a \; mod\; N$ .

Так как s мы не знаем, Поллард предложил сравнивать x_n и $x_{2n}$ . Таким образом, алгоритм состоит в последовательной проверке всех n на то, что $gcd(x_n - x_{2n}, N)$ является нетривиальным делителем N. Сложность такого алгоритма - $O(\sqrt{N})$ .

Метод Брента

В 1980 году Ричард Брент опубликовал статью "An improved Monte Carlo factorization algorithm", в которой предложил улучшение ро-алгоритма Полларда.

Отличие заключается в том, что вместо $gcd(x_n - x_{2n}, N)$ мы ищем делитель в виде gcd(x_n - x_m, N) , где m - наибольшее целое число удвлетворяющее $2^m \le n$ .

Последовательность тоже задается по другому:

$x_0 \equiv 2 \; mod\; N$

$x_{n+1} \equiv x_n^2 + 2\; mod\; N$

Как и в алгоритме Полларда существуют и другие различные варианты задания такой последовательности. Результатом такого улучшение стало уменьшение сложности: $O(N^{1/4})$ .

p-1 алгоритм факторизации Полларда

В 1974 году Поллард опубликовал еще один алгоритм. Он основан на малой теореме Ферма:

Если p - простое число, являющееся делителем натурального числа a, то $a^{p-1} \equiv 1\; mod\; p$ .

Для понимания алгоритма нужно сделать еще один математический шаг: пусть есть число $k \ge 1$ , такое что p-1 - делитель . Можем переписать как (p-1)q по свойству факториала. Таким образом: $2^{k!} \equiv (2^{p-1})^q \equiv 1^q \equiv 1\; (mod\; p)$ . Получаем, что - делитель $2^{k!}-1$ . Мы можем искать делитель в виде $gcd(2^{k!}-1, N)$ , в этом и состоит алгоритм.

В данном случае сложно явно определить сложность не вдаваясь в сложную математику, но условно сложность можно записать как $O(\sqrt{N}\log^c{N})$ .

Сравнение производительности алгоритмов

Следующий график показывает количество итераций разных алгоритмов для N разного порядка:

Производительность алгоритмов факторизации

Вывод

На графике видно, что факторизация чисел порядка 10^6 требует порядка 1000 итераций. Нахождение нового, еще более производительного алгоритма не только может заработать создателю 200,000$, но и, быть может, позволит ему взломать современные алгоритмы шифрования, а следовательно, улучшить их.

Ссылки на используемые материалы

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.117.1230&rep=rep1&type=pdf https://en.wikipedia.org/wiki/RSA_Factoring_Challenge https://en.wikipedia.org/wiki/Computational_complexity_theory https://ru.wikipedia.org/wiki/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D1%84%D0%B0%D0%BA%D1%82%D0%BE%D1%80%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D0%B8_%D0%A4%D0%B5%D1%80%D0%BC%D0%B0 https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm https://archive.lib.msu.edu/crcmath/math/math/p/p440.htm http://mathworld.wolfram.com/PollardRhoFactorizationMethod.html https://maths-people.anu.edu.au/~brent/pd/rpb051i.pdf https://en.wikipedia.org/wiki/Fermat%27s_little_theorem https://ru.wikipedia.org/wiki/%D0%A4%D0%B0%D0%BA%D1%82%D0%BE%D1%80%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F_%D1%86%D0%B5%D0%BB%D1%8B%D1%85_%D1%87%D0%B8%D1%81%D0%B5%D0%BB

Hubs:

Popular science