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

[nnosipov]

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

Взял от фонаря $p=234259$, $q=2344253$

А что получится в этом случае, если применить Ваш алгоритм для $N=pq$? Как быстро будет найден $p$?

[Руст]

Пример опровержение попроще. Пусть $N=p(p+1)$ и $n=p+2$, тогда $m=p, r=p$. Проверяем ваше неравенство $p\le p+3-[\frac{\sqrt{Nr}}{m}]=p+3-[\sqrt{p+1}]$ не работает при $p\ge 15$. Можно привести и другие примеры, например:
$N=p(3p+2),n=p+1\to m=3p, r=p$ и $p\le p+2-[\frac{\sqrt{Nr}}{m}]=p+2-[\frac{\sqrt{3p+2}}{3}]$ не работает при $p\ge 27$.

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

Руст в сообщении #625643 писал(а):

Пример опровержение попроще. Пусть $N=p(p+1)$ и $n=p+2$, тогда $m=p, r=p$. Проверяем ваше неравенство $p\le p+3-[\frac{\sqrt{Nr}}{m}]=p+3-[\sqrt{p+1}]$ не работает при $p\ge 15$.

Этот пример отпадает, так как $n$ изначально является делителем $N$.

Руст в сообщении #625643 писал(а):

$N=p(3p+2),n=p+1\to m=3p, r=p$ и $p\le p+2-[\frac{\sqrt{Nr}}{m}]=p+2-[\frac{\sqrt{3p+2}}{3}]$ не работает при $p\ge 27$.

Мы знаем только число $N$, откуда вы знаете, что $n=p+1$? Но даже если вы и угадали такое $n$, то $m$ вычисляется следующим образом: $m=[\frac{N}n]+1$

[nnosipov]

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

... то $m$ вычисляется следующим образом: $m=[\frac{N}n]+1$

И получаем в точности $m=3p$. Итак, Ваше неравенство неверно.

[dmd]

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

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

Взял от фонаря $p=234259$, $q=2344253$

А что получится в этом случае, если применить Ваш алгоритм для $N=pq$? Как быстро будет найден $p$?

poal()=
{

p= 234259; q= 2344253; N= p*q; n= sqrtint(N); i= 1;

while(n>(p-10),
 r= -N%n;
 m= (N+r)/n;
 a= floor(sqrt(N*r)/m)-1;
 n= n-a-1;
 print("i = ",i,"    n= ",n);
 i++;
)

};

Порядка двух тысяч циклов, при этом через $p$ перешагнуло, т.е. алгоритм не сошёлся к $p$.

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

Спасибо всем за полезное для меня обсуждение. Есть над чем подумать...
Уважаемый Руст, какие еще возможные нарушения работы неравенства существуют, кроме $n=p+1, m=3p, r=p$. Просто хочу понять, где прокол в моих рассуждениях. Возможно есть более жесткие ограничения на остаток...

[Руст]

Когда $n$ порядка $\sqrt N$ или меньше, особых ограничений на ближайший простой делитель р, меньше n, не существует.

[Sender]

Руст в сообщении #625967 писал(а):

Когда $n$ порядка $\sqrt N$ или меньше, особых ограничений на ближайший простой делитель р, меньше n, не существует.

Да и не только на простой. Например, для чисел вида $N=(n-1)(n+2)$ число $\lfloor \sqrt{N} \rfloor$ при $n>2$ не является делителем N, а $\lfloor \sqrt{N} \rfloor-1$ - является.

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

Хочу привести ход своих рассуждений, может подскажете, где ошибка...
Я исходил из такого тождества:
$(n-a)(m+\frac{ma}n)=nm-\frac{ma^2}n$
Если предположить, что $\frac{ma^2}n<r$, то соответственно $a<\sqrt{\frac{nr}m$
Пусть $a=[\sqrt{\frac{nr}m}]$, я делаю вывод, что $p<n-a$
Не пойму, почему неравенство не срабатывает...

[dmd]

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

$\frac{\sqrt{Nr}}m$

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

$\sqrt{\frac{nr}m$

Если последний $n$ есть первый $N=pq$ и если под радикалом на самом деле дробь $\frac{Nr}{m}$, то Ваш алгоритм ускоряется в 1000 раз, вместо 2000 циклов вычислений получаются всего два, т.е. стартуя от $\sqrt N$ алгоритм доходит до границы около $p$ за два шага вычислений. Но всё равно сходимости нет, значение $p$ не находится.

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

В тех обозначениях, которые были введены
$pq=N=nm-r$, причем $p<q, n<m, p<n, 0<r<n$
Поэтому ваша замена $n$ на $N$ не корректная.
Я хочу порассуждать еще. Самое маленькое значение $a=1$.
Распишем для него выражение $(n-1)(m+1)=nm-(m-n+1)$.
Получается, что при $r<m-n+1$ правило выбора $a$ неопределено. Можно только точно сказать, что это не единица. Значит в таком случае будем выбирать $a=2$.
Соответственно, если $r=m-n+1$, то $a=1$ и можно просто точно указать делитель.
Если $r>m-n+1$, то $a=[\sqrt{\frac{nr}m}]$.
Но $m-n+1<r<n$. Отсюда следует, что оценка сверху меньшего делителя будет работать при условии $m<2n-1$. Поэтому пример Руста не срабатывал.

[Руст]

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

Но $m-n+1<r<n$. Отсюда следует, что оценка сверху меньшего делителя будет работать при условии $m<2n-1$. Поэтому пример Руста не срабатывал.

Почему же не срабатывал, это ваш закон не срабатывает. Примеры указывает, когда не срабатывает. Пожалуйста другой пример. $N=p(2p-1),n=p+1\to m=2p-2, r=p-2$. Ваша формула дает $p\le p+2-[\frac{\sqrt{p(2p-1)(p-2)}}{2p-2}]\le p-1$, если $p(p-2)(2p-1)\ge 36(p-1)^2$, т.е при $2p^3-41p^2+74p\ge 36$ ваша формула не работает для данного примера, т.е. при $p\ge 20$.

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

Руст, обращаю ваше внимание на условие применимости моей формулы.
$m-n+1=(2p-2)-(p+1)+1=p-2=r$
В данном случае $a=1$, и можно конкретно указать делитель $p=n-1$.
Так что этот пример не проходит.