К вопросу факторизации чисел

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

Пусть $N$ нечётное натуральное число и яляется произведением двух простых чисел $p$ и $q$, причем $p$ меньше $q$.
Обозначим $n=[\sqrt{N}]$, где [] - целая часть числа $N$.

Тогда существуют натуральные числа, a и b такие, что
$p=[\sqrt{N}]-a=n-a$,
$q=[\sqrt{N}]+a+2\cdot b=n+a+2\cdot b$
То есть число $N$ можно представить так:
$N=p\cdot q=(n-a)(n+a+2\cdot b)$

Более того, число $a$ можно выразить через число $b$.
$a=\sqrt{(n+b)^2-N}-b$
Сответственно
$p=(n+b)-\sqrt{(n+b)^2-N}$
$q=(n+b)+\sqrt{(n+b)^2-N}$

Перебирая значения $b$ от 1 до числа, когда под корнем будет полный квадрат и исчезнет корень, мы факторизуем заданное число $N$.
Можно ли оптимизировать процесс перебора $b$?

Давайте рассмотрим другую запись меньшего множителя числа $N$.
$p=\frac{a^2+(N-n^2)}{2\cdot b}$ только представим в виде $p\cdot b=\frac{a^2+(N-n^2)}2$
Обозначим $R=N-n^2$
$p\cdot b=\frac{a^2+R}2$
Из этой записи видно, что $a$ и $R$ должны быть одинаковой четности, иначе справа будет дробь, чего быть не должно, так как слева перемножаются натуральные числа.

Рассмотрим два случая.

1. $a$ и $R$ чётные.
Тогда $a=2\cdot a_0, R=2\cdot r$
$p\cdot b=\frac{a^2+R}2=\frac{(2\cdot a_0)^2+2\cdot r}2=2\cdot (a_0)^2+r$
Вывод:
если$(\frac{R}2)$ - четное, то и $b$ - четное,
если $(\frac{R}2)$ - нечетное, то и $b$ - нечетное.

2. $a$ и $R$ нечётные.
Пусть $a=2\cdot a_0-1$, тогда
$p\cdot b=\frac{a^2+R}2=\frac{(2\cdot a_0-1)^2+R}2=\frac{(4\cdot (a_0)^2-4\cdot a_0+1)+R}2=2\cdot (a_0)^2-2\cdot (a_0)+\frac{R+1}2$
$p\cdot b=2\cdot (a_0)\cdot(a_0-1)+\frac{R+1}2$
Вывод:
если $(\frac{R+1}2)$ - нечетное, то и $b$ - нечетное,
если $(\frac{R+1}2)$ делится только на 2, то $b$ - четное,
если $(\frac{R+1}2)$ делится на 4, то и $b$ кратное 4.

Пример.
$ N=114557, n=[\sqrt{N}]=338, R=N-n^2=313$ нечетное.
$\frac{R+1}2=\frac{313+1}2=157$ нечетное.
Следовательно, меньший множитель будем искать по формуле вида
$p=(n+b)-\sqrt{(n+b)^2-N}=(n+(2\cdot b_0-1))-\sqrt{(n+(2\cdot b_0-1))^2-N}$
при $b_0=151, b=301$ будет полный квадрат и, соответственно, $p=97$, $q=1181$.

[Andrey A]

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

Следовательно, меньший множитель будем искать по формуле вида
$p=(n+b)-\sqrt{(n+b)^2-N}=(n+(2\cdot b_0-1))-\sqrt{(n+(2\cdot b_0-1))^2-N}$

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

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

Это и есть метод Ферма.
Некоторое его усовершенствование должно пойти только на пользу.
Или выигрыш в два раза малосущественная величина?
Может мои рассуждения подтолкнут к более серьезным усовершенствованиям.

[Someone]

Почитайте о методе Ферма (алгоритм C) и методе решета (алгоритм D) у Д. Кнута (Искусство программирования для ЭВМ, т. 2. Получисленные алгоритмы. "Мир", Москва, 1977.), раздел 4.5.4.

[Andrey A]

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

Или выигрыш в два раза малосущественная величина?

Да нет, всё нормально. Только на языке сравнений всё это выражается проще. Положительное нечетное $N$ есть разность двух квадратов разной четности. Если $N$ дает остаток $3$ при делении на $4,$ то старший квадрат четный, если же $N \equiv 1 \mod 4,$ как в Вашем примере, то старший квадрат нечетный. Это происходит потому, что квадраты при делении на $4$ могут давать в остатке либо $0$, либо $1.$ То же и по $\mod 3:\ 114557 \equiv 2 \mod 3.$ Единственно возможный вариант $0-1 \equiv 2 \mod 3,$ значит старший квадрат кратен трем. По $\mod 5$ тоже $114557 \equiv 2$, но набор квадратичных вычетов другой: $1,0,-1.$ Тут только так: $1-(-1) \equiv 2 \mod 5.$ Следовательно оба квадрата не делятся на $5.$ Таким образом основание старшего квадрата есть нечетное число кратное трем и не кратное пяти, то есть $\pm 3,\pm 9 \mod 30.$ Можно перебирать только их. Можно и по другим модулям смотреть, но муторно. Всё равно ведь быстрой факторизацией это не назовешь.

Upd

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

то есть $\pm 3,\pm 9 \mod 30.$

Точнее так: $\pm 9 \mod 30,$ поскольку $(\pm 3)^2 \equiv -1 \mod 5,$ а нужна единица. Всё это верно, кстати, и относительно тривиальной пары квадратов, на которую можно ориентироваться как на частный случай. По маленьким модулям даже удобно.

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

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

Почитайте о методе Ферма (алгоритм C) и методе решета (алгоритм D) у Д. Кнута (Искусство программирования для ЭВМ, т. 2. Получисленные алгоритмы. "Мир", Москва, 1977.), раздел 4.5.4.

Someone, спасибо за подсказку по теме. Уже информацию нашёл и знакомлюсь

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

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

Или выигрыш в два раза малосущественная величина?

Да нет, всё нормально. Только на языке сравнений всё это выражается проще. Положительное нечетное $N$ есть разность двух квадратов разной четности. Если $N$ дает остаток $3$ при делении на $4,$ то старший квадрат четный, если же $N \equiv 1 \mod 4,$ как в Вашем примере, то старший квадрат нечетный. Это происходит потому, что квадраты при делении на $4$ могут давать в остатке либо $0$, либо $1.$ То же и по $\mod 3:\ 114557 \equiv 2 \mod 3.$ Единственно возможный вариант $0-1 \equiv 2 \mod 3,$ значит старший квадрат кратен трем. По $\mod 5$ тоже $114557 \equiv 2$, но набор квадратичных вычетов другой: $1,0,-1.$ Тут только так: $1-(-1) \equiv 2 \mod 5.$ Следовательно оба квадрата не делятся на $5.$ Таким образом основание старшего квадрата есть нечетное число кратное трем и не кратное пяти, то есть $\pm 3,\pm 9 \mod 30.$ Можно перебирать только их. Можно и по другим модулям смотреть, но муторно. Всё равно ведь быстрой факторизацией это не назовешь.

Upd

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

то есть $\pm 3,\pm 9 \mod 30.$

Точнее так: $\pm 9 \mod 30,$ поскольку $(\pm 3)^2 \equiv -1 \mod 5,$ а нужна единица. Всё это верно, кстати, и относительно тривиальной пары квадратов, на которую можно ориентироваться как на частный случай. По маленьким модулям даже удобно.

Andrey A, я тоже рассматривал вариант с остатками по модулю $3$. Но в этом случае не получается одна формула. Другими словами надо создавать программу, которая будет отсекать ненужные числа и оставлять подходящие. Либо пробегать значения сначала по первой формуле, затем по следующей и так далее. Когда есть одна формула, как у меня, то проверив до какого-то значения $b=A$ мы точно знаем, что не пропустили искомого множителя.

[Andrey A]

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

... с остатками по модулю $3$. Но в этом случае не получается одна формула.

Почему же. Квадраты при делении на $3$ дают в остатке либо $1,$ либо $0$. Если $N$ не делится на $3,$ возможны строго два случая:

$1-0 \equiv 1 \mod 3.$

$0-1 \equiv 2 \mod 3,$ как в Вашем примере.

Я бы рекомендовал Гаусса почитать. Он сам эту теорию создал и уж точно ничего не упустил. "Труды по теории чисел". Да и переведено качественно, просто читать интересно.
Лет тридцать назад ради этого ехали в читальный зал. Если не очень далеко.

[cheslav]

Может ли быть практическая польза от следующих рассуждений?
"Для того чтобы уравнение пятой степени (9) разлагалось на множители (10) необходимо чтобы выполнялось равенство (11):

$$x^5+Ax^3+Bx^2+Cx+D=0,\eqno(9)$$

$$(x^2+px+q)(x^3-px^2+mx+n)=0,\eqno(10)$$

$$D^2+(B^2)C=ABD.\eqno(11)$$

которое получается если перемножить сомножители в (10) и приравнять полученные коэффициенты с соответствующими
из (9).Это условие тождественно утверждению теоремы Абеля о том,что не всякое уравнение степени выше четвёртой может иметь корни.Для уравнения шестой степени соответствующее условие факторизации будет иметь вид:

$$x^6+Ax^4+Bx^3+Cx^2+Dx+E=0,$$

$$D^3+A(B^2)(D^2)+E(B^3)=(B^2)CD.$$

"

[nnosipov]

cheslav в сообщении #1523302 писал(а):

Может ли быть практическая польза от следующих рассуждений?

Нет. К задаче факторизации целых чисел это вообще не имеет никакого отношения.