Оценка снизу наименьшего делителя числа

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

Уважаемые софорумники! Выношу на ваше обсуждение следующие мои изыскания в области факторизации чисел.
Исследуемый вопрос стоит так: можно ли оценить пределы, в которых следует искать минимальный множитель?
Пусть задано число $ N=pq$, где $p<q$, $p,q$-простые числа.
Требуется найти такие оценки $a,b$, что $1<a\le p\le b<\sqrt{N}$.
Для оценки сверху простого числа $p$ предлагается такая формула $b=[\sqrt{N}]-[\sqrt{(([\sqrt{N}]+1)^2-N)}]$, квадратные скобки означают целую часть числа.
Для оценки снизу простого числа $p$ производятся следующие вычисления:
число $N$ представляется в виде $N=k^4+4m^4+r$, сначала подбираем такое максимальное $k$, что $k^4<N$, затем при зафиксированном $k$ подбираем такое максимальное $m$, что $k^4+4m^4<N$. Такой подбор можно сделать всегда.
Оценка меньшего делителя $a=(k-m)^2+m^2)<p$.
Пример:
$17*53=901=30^2+1=31^2-60=5^4+4*3^4+33$
$(5-3)^2+3^2\le 17\le 30-7$
$13\le 17\le 23$

Оценка сверху выполняется во всех случаях, а вот оценка снизу может давать сбой, когда простые числа$p$ и $q$ сильно отличаются по величине.
Прошу высказывать свои мнения по теме, с удовольствием приму критические замечания.

[maxal]

Имея оценку $a\leq p\leq b$, её всегда можно уточнить так:

$$\frac{N}{b} \leq q \leq \frac{N}{a}$$

и так как $q$ - целое, то

$$\left\lceil\frac{N}{b}\right\rceil \leq q \leq \left\lfloor\frac{N}{a}\right\rfloor,$$

а поэтому:

$$\left\lceil\frac{N}{\lfloor N/a\rfloor}\right\rceil \leq p \leq \left\lfloor\frac{N}{\lceil N/a\rceil}\right\rfloor.$$

Но чтобы дойти до нахождения $p$ таким образом, всё равно потребуется экспоненциальное (от длины $N$) число шагов.

[Батороев]

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

Оценка сверху выполняется во всех случаях, а вот оценка снизу может давать сбой, когда простые числа$p$ и $q$ сильно отличаются по величине.
Прошу высказывать свои мнения по теме, с удовольствием приму критические замечания.

Оценка снизу может давать сбой, когда простые числа$p$ и $q$ сильно отличаются по величине, а оценка сверху может давать сбой, когда простые числа$p$ и $q$ не сильно отличаются по величине?! Так? Например, $N=899$.

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

Уважаемый, Батороев! Вариант разность квадратов я исключил, как очевидный. Если это принципиально, то в формулу просто добавим единичку.Но за замечание спасибо! ))

-- Вт апр 26, 2011 11:21:11 --

Уважаемый, maxal! Не подскажете, какие еще существуют оценки для делителей?