Быстрая факторизация

[Побережный Александр]

Факторизация числа считается трудоемкой операцией.
Предлагаю к обсуждению свои размышления на эту тему.

Пусть задано некоторое нечетное составное число $N=pq$, причем $p<q$.
Тогда существует такое натуральное число $k$, что
$p=\sqrt{N+k^2}-k$
$q=\sqrt{N+k^2}+k$
Следовательно, делители числа определяются, если вычислим арифметический корень.
Рассмотрим число $N$ специального вида так, чтобы получился полный квадрат под корнем. Тогда делители быстро вычисляются.
$N=(m^2-1)k^2+2mk+1$, где m - натуральное число
$p=\sqrt{N+k^2}-k=\sqrt{(m^2-1)k^2+2mk+1+k^2}-k=mk+1-k=(m-1)k+1$
$q=\sqrt{N+k^2}+k=\sqrt{(m^2-1)k^2+2mk+1+k^2}+k=mk+1+k=(m+1)k+1$
Насколько я представляю, не все составные числа можно представить в указанной форме.
Но если это удастся, то факторизация удалась.

Пример:
$N=247$, $m=5$, $k=3$
$247=(5^2-1)3^2+2\cdot5\cdot3+1$.
Данное число требуемой формы, следовательно $p=(5-1)3+1=13$, $q=(5+1)3+1=19$
$13\cdot19=247$

Аналогичные рассуждения будут для чисел вида $N=(m^2-1)k^2-2mk+1$ (с минусом).

[Dmitriy40]

Чего-то я не понял, так как найти $k$ по известному $N$? Например для $N=69424939$? Или Вы решили обратную задачу - сформировать множество чисел специального вида, удобно разложимых на пару множителей? Так она вообще ни разу не интересна и тривиальна.

[Pavia]

Побережный Александр в сообщении #1339379 писал(а):

Тогда существует такое натуральное число $k$, что
$p=\sqrt{N+k^2}-k$
$q=\sqrt{N+k^2}+k$

Откуда Вы это взяли?

[kotenok gav]

Побережный Александр в сообщении #1339379 писал(а):

арифметический корень.

Это вообще секундное дело.

[Dmitriy40]

Pavia в сообщении #1339387 писал(а):

Откуда Вы это взяли?

А можете привести контрпример (кроме неподходящего по условию $N=1$)? Что-то я для $N<500000$ контрпримера не нашёл, $k$ для извлекаемости корня вполне себе находятся. Или это открытая проблема? А, похоже это прямо следует из существования разложения на множители $N=(a-k)(a+k)(...), a=\sqrt{N+k^2}$, первая скобка равна $p$, вторая $q$.

[Someone]

Побережный Александр в сообщении #1339379 писал(а):

Пусть задано некоторое нечетное составное число $N=pq$, причем $p<q$.
Тогда существует такое натуральное число $k$, что
$p=\sqrt{N+k^2}-k$
$q=\sqrt{N+k^2}+k$

Ну да, если число $N$ разлагается в произведение двух нечётных множителей $p$ и $q$, где $p<q$, то можно взять $k=\frac 12(q-p)$, Тогда $\sqrt{N+k^2}=\frac 12(q+p)$.

Вообще-то, это методом Ферма называется: для разложения нечётного числа на множители ищется его представление разностью квадратов. Если есть множитель, достаточно близкий к $\sqrt{N}$, то этот метод помогает.

Dmitriy40 в сообщении #1339383 писал(а):

Чего-то я не понял, так как найти $k$ по известному $N$? Например для $N=69424939$?

Ну что значит — как. Как Ферма велел.

Метод можно применять не только к самому числу $N$, но и к его кратным $mN$. В качестве множителя $m$ следует брать нечётные числа и числа, кратные $8$.

[Andrey A]

Побережный Александр в сообщении #1339379 писал(а):

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

Если $q=(m+1)k+1,\ p=(m-1)k+1$, то $\frac{q-1}{p-1}=\frac{m+1}{m-1}$ и $\frac{q+p-2}{q-p}=m.$ Положите $m$ рациональным числом, тогда все нечетные составные можно представить в указанной форме. Домножив всё на квадрат знаменателя (если не понравилось), получаем более общую форму в целых числах. В принципе любое число можно домножить на некий целый квадрат чтобы работал метод Ферма, что и достигается разложением $\sqrt{N}$ в непрерывную дробь (уравнение Пелля). Однако же без гарантии. Уже для $N=119$ решение оказывается тривиальным: $120^2-119\cdot 11^2=1$, да и нужный квадрат может оказаться слишком большим.

[Someone]

Andrey A, а зачем так сложно? Если $N=pq$, где $p$ и $q$ — числа одинаковой чётности, $p<q$, то $N=\left(\frac{q+p}2\right)^2-\left(\frac{q-p}2\right)^2$. Обе дроби в скобках — натуральные числа.

В частности, $119=7\cdot 17$, поэтому получаем $119=12^2-5^2$. Методом Ферма эту разность квадратов можно найти: полагаем $x_0=[\sqrt{119}]=11$, $x_k=x_0+k$, и вычисляем $x_k^2-N$, пока не получим точный квадрат. Здесь уже $x_1=12$ и $x_1^2-N=144-119=25=5^2$.
Но для столь малых чисел это не интересно. Интереснее, например, для числа $N=69\,424\,939$, которое предложил Dmitriy40.

Метод Ферма имеет много усовершенствованных вариантов, в том числе и цепные дроби можно использовать.

[Andrey A]

Someone в сообщении #1339525 писал(а):

... так сложно

Если имеется в виду разложение квадратного радикала в целях факторизации, это конечно сложно. Метод Ферма хороший. Простой и надежный, однако имеется недостаток -- унылый перебор значений, который вне зависимости от результата оставляет всякий раз чувство легкой неудовлетворенности. Как умножить $a$ на $b$ мы знаем точно, но обратный шаг можем сделать лишь вслепую, и эта необратимость умножения возбуждает фантазию. Детский вопрос: умножая, получаем из нескольких чисел одно. Обратно должны получить из одного несколько, но даже не знаем сколько. Ну хотя бы два, это возможно? Вот как раз решая Пелля, получаем из одного два :)

Someone в сообщении #1339525 писал(а):

Метод Ферма имеет много усовершенствованных вариантов, в том числе и цепные дроби можно использовать.

Нельзя ли поподробней? Что-то об этом у Шамиля Ишмухаметва написано, но вроде бы тот же Пелль с подстановкой $m \rightarrow km$, и опять перебор.

[Someone]

Andrey A в сообщении #1339558 писал(а):

Нельзя ли поподробней?

Объяснять это здесь слишком длинно. Некоторый обзор можно посмотреть в Википедии. Подробности обычно лучше искать в специальной литературе. Кое что можно найти, например, во втором томе "Искусства программирования для ЭВМ" Д. Кнута.

Сам метод Ферма выглядит так (на примере числа $N=69\,424\,939$).
Вычисляем $x_0=\left[\sqrt{69\,424\,939}\right]=8\,332$, убеждаемся, что $N$ не является точным квадратом, и составляем таблицу:

\begin{tabular}{|c|c|c|c|} \hline $k$ & $x_k$ & $2x_k+1$ & $x_k^2-N$\\ \hline $1$ & $8\,333$ & $16\,667$ & $13\,950$\\ \hline $2$ & $8\,334$ & $16\,669$ & $30\,617$\\ \hline $3$ & $8\,335$ & $16\,671$ & $47\,286$\\ \hline $4$ & $8\,336$ & $16\,673$ & $63\,957$\\ \hline $5$ & $8\,337$ & $16\,675$ & $80\,630$\\ \hline $6$ & $8\,338$ & $16\,677$ & $97\,305$\\ \hline $7$ & $8\,339$ & $16\,679$ & $113\,982$\\ \hline $8$ & $8\,340$ & $16\,681$ & $130\,661$\\ \hline $9$ & $8\,341$ & $16\,683$ & $147\,342$\\ \hline $10$ & $8\,342$ & $16\,685$ & $164\,025$\\ \hline $\vdots$ & $\vdots$ & $\vdots$ & $\vdots$\\ \hline \end{tabular}

После того, как вычислена величина $x_1^2-N$, следующие значения вычисляются без возведения в квадрат, просто сложением: $x_{k+1}^2-N=(x_k^2-N)+(2x_k+1)$. Отсеять бо́льшую часть разностей, не являющихся точными квадратами, можно по двум последним цифрам: квадрат целого числа может оканчиваться на

$$00,01,04,09,16,21,24,25,29,36,41,44,49,56,61,64,69,76,81,84,89,96$$

(можно сформулировать более компактное правило).
В частности, в указанной таблице квадратами могут быть только $x_8^2-N$ и $x_{10}^2-N$. Проверка показывает, что квадратом является только $x_{10}^2-N=164\,025=405^2$, поэтому

$$N=8\,342^2-405^2=(8\,342-405)(8\,342+405)=7\,937\cdot 8\,747.$$

Если взять число $N$ побольше, все делители которого сильно отличаются от $\sqrt{N}$, то метод Фурье будет работать плохо.
Всякие усовершенствования метода Фурье обычно называются другими именами.

[Andrey A]

Спасибо, тут всё понятно. Поскольку ТС молчит, думаю, не обидится на легкий оффтопик. Правую колонку полезно проверять еще по $\mod 8\ (0,1,4)$. В частности $x_8=130661 \equiv 5 \mod 8$ не годится. Старшие квадраты тоже можно брать не любые, смотря хотя бы по $\mod 3$ и $\mod 4$. В данном случае ясно что старший квадрат должен делиться на $2$ и не должен делиться на $3$, т.е. $\pm 2 \mod 6$ - еще $67$% экономии. И все-таки если бы $N$ не оказалось произведением двух близких простых (в чем еще надо убедиться), табличка могла растянуться до пола. Можно вместо квадратов брать треугольники (суммы натурального ряда), там для нечетных модулей в два раза больше нетривиальных отображений, да мало-ли чего еще можно придумать. Меня заинтересовало как можно метод Ферма с цепными дробями поженить, но это был бы уже большой оффтопик. В Вашей ссылке ничего об этом не нашел, зато встретил такое: По данным двум числам можно найти их произведение простым и надёжным способом, но совсем другое дело, когда для большого числа необходимо найти его множители. Можно ли сказать, какие два числа перемножены, чтобы получилось число 8 616 460 799? Я думаю, что вряд ли кто-либо кроме меня знает это. Да это же прямо из моего поста! Бросая камешки в воду...

[Someone]

Andrey A в сообщении #1339713 писал(а):

Правую колонку полезно проверять еще по $\mod 8\ (0,1,4)$. В частности $x_8=130661 \equiv 5 \mod 8$ не годится. Старшие квадраты тоже можно брать не любые, смотря хотя бы по $\mod 3$ и $\mod 4$.

Да, это известно. Проверка по последним цифрам очень проста, а по другим модулям требуется деление для вычисления остатка.
Но можно заранее "просеять" по нескольким модулям и использовать результаты, чтобы проверять не все $x_k$ подряд. Если Вы почитаете Д. Кнута, Вы там этот метод найдёте.

Andrey A в сообщении #1339713 писал(а):

Меня заинтересовало как можно метод Ферма с цепными дробями поженить

Д. Кнута читайте.

[Andrey A]

Ладно, спасибо.

[Dmitriy40]

(Оффтоп)

Someone в сообщении #1339725 писал(а):

Д. Кнута читайте.

К своему стыду не помню что это есть у Кнута, хотя и читал его лет 15 назад, но видимо слишком поверхностно и многое забылось.

[Someone]

(Оффтоп)

Dmitriy40 в сообщении #1339738 писал(а):

К своему стыду не помню что это есть у Кнута, хотя и читал его лет 15 назад, но видимо слишком поверхностно и многое забылось.

Скорее всего, Вас мало интересовало разложение натуральных чисел на простые множители, а алгоритмы там специфические, поэтому и не запомнилось.

Кстати, Д. Кнут демонстрирует применение метода Ферма с предварительным просеиванием по нескольким модулям на примере именно вот этого числа:

Andrey A в сообщении #1339713 писал(а):

8 616 460 799