Оценка сверху наименьшего делителя

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

Путем некоторых рассуждений получил любопытный результат.
Пусть $pq=N=nm-r$, где $p<q, n<m, p<n$, тогда
$p \leqslant n+1-[\frac{\sqrt{Nr}}m]$
Некоторые ограничения: $N$ и $r$ не являются полными квадратами. В этом случае множитель $p$ легко вычисляется.

[nnosipov]

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

Пусть $pq=N=nm-r$, где $p<q, n<m, p<n$, тогда
$p \leqslant n+1-[\frac{\sqrt{Nr}}m]$

Это неверно. Взял от фонаря $p=234259$, $q=2344253$, $m=4564571$, $n=324435$ и не получил Вашего неравенства.

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

Видимо я не корректно сформулировал...
$r$ - это остаток от деления числа $N$ на число $n$.
Я почему-то думал, что использую общепринятую запись.
$0<r<n$

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

nnosipov в сообщении #625024 писал(а):

Взял от фонаря $p=234259$, $q=2344253$, $m=4564571$, $n=324435$ и не получил Вашего неравенства.

В вашем примере расчеты следующие:
$p=234259$, $q=2344253$, $N=pq=549162363527$, $n=324435$, $m=1692673$, $r=1228$
$[\frac{\sqrt{Nr}}m]=15$
Так что формула работает.
Еще раз напоминаю, $m$ и $r$ величины вычисляемые.

[nnosipov]

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

Видимо я не корректно сформулировал...
$r$ - это остаток от деления числа $N$ на число $n$.

Опять плохо сформулировали: последняя фраза противоречит равенству $N=mn-r$.

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

Так что формула работает.

Возможно, а какая с неё польза? Пример показывает, что оценка для $p$ плохая.

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

Еще раз напоминаю, $m$ и $r$ величины вычисляемые.

Это Вы в первый раз сообщаете.

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

Для меня проблема оценки делителя возникла, когда попыталься факторизовать большие числа. Простой перебор, как вы сами понимаете, не метод. Хотя формально обеспечивает 100% - ю достоверность результата. Значит следует делать скачки через определенный интервал чисел. Но произвольно выбирать интервал нельзя, можно проскочить искомый делитель. Вот и возникла задача - сформулировать оценку сверху наименьшего делителя. Почему сверху, а не снизу? Просто так легче реализовалось. Об оценке снизу я еще подумаю...
Сам алгоритм следующий: число $n$, которое должно быть заведомо больше или равно делителю $p$ всегда можно указать, например $n=[\sqrt{N}]$, дальше вычисляем интервал скачка, где точно нет делителя, обозначим его $a=[\frac{\sqrt{Nr}}m]-1$. Число $n-a$ точно не делитель, а вот $n-a-1$ уже может быть делителем. Проверяем его, если это не делитель, то это число становится нашим новым $n$ для которого строится свои $m$ и $r$. Процедура снова повторяется. Только появление делителя процедуру прерывает.
Я не утверждаю, что это оптимальный алгоритм, но обращаю внимание - в алгоритме нет процедуры поиска простых чисел. И еще, искать делитель можно и на обычном калькуляторе, самое сложное действие - это извлечение квадратного корня.

[Руст]

Цель хорошая, но она не реализована.
Пусть $N=p^2+1$. Вы выбираете $n=\lceil \sqrt{N}\rceil =p+1$, соответственно $m=p,r=p-1$.
Однако не верно ваше неравенство:
$p\le p+2-[\sqrt{(p^2+1)(p-1)}{p}]=p+2-[\sqrt{p-1}]$, когда $p>9$.
Я тут забыл, что р делитель. Надо привести другой пример, который уже сделал Someone.

[Someone]

Берём $N=19\cdot 23=437$. Вычисляем: $n=[\sqrt{437}]=20$, $r\equiv 17\pmod{n}$, $m=\frac{437-17}{20}=21$, $a=\left[\frac{\sqrt{437\cdot 17}}{21}\right]-1=3$, $p\leqslant 20-3=17$. В то время как $p=19$. Что-то не так.

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

Someone, $N=nm-r$. Соответственно $n=20, m=22, r=3$. Следовательно $a=0$.
Все проходит.

[Someone]

Ну, Вы формулой пишете одно, а словами говорите другое.

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

Остаток от деления, по определению, может быть и отрицательным числом.
http://ru.wikipedia.org/wiki/%D0%94%D0%B5%D0%BB%D0%B5%D0%BD%D0%B8%D0%B5_%D1%81_%D0%BE%D1%81%D1%82%D0%B0%D1%82%D0%BA%D0%BE%D0%BC
У меня как раз именно тот случай.

[Someone]

Дык, предупреждать надо. И даже если остаток $r$ отрицательный - всё равно в формуле будет $N=nm+r$, а не $N=nm-r$.

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

Согласен, не совсем корректно определил. Надеюсь, теперь понятно, как используется формула? Все переменные у меня натуральные числа, в том числе и $r$. Но в формуле использую запись с минусом.

[Someone]

Тогда просто не говорите, что $r$ - остаток.

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

Просто на $r$ лежат те же ограничения, $0\leqslant r<n$