Вопрос про метод факторизации ферма

[jivar]

Добрый день. Не могу понять, почему метод ферма хорошо факторизует числа с примерно равными множителями?

Пусть n=ab.
Как того требует алгоритм, положим
$x=integerpart(sqrt(n)), y=x^2 - n$
И будем увеличивать х на единицу, пока не получим полный квадрат у. Если преобразовать у, то получиться(к-номер итерации):

$y=2k*sqrt(ab)+k^2$

Так где же здесь всплывает то, что при близких а и б, у быстрее окажеться полным квадратом?

[AV_77]

Пусть $y = z^2$. Тогда $n = x^2 - y^2 = (x-z)(x+z) = ab$ - разложение на множители, $a > b$. Отсюда $x = \frac{a+b}{2}$ и $z = \frac{a-b}{2}$ и видно, что если $a$ и $b$ близки, то $\sqrt{n}$ находится рядом с $\frac{a+b}{2}$.

[jivar]

Спасибо большое.
И еще такой вопрос, как измениться диапазон перебора х, если известно, что а примерно равно 2b? Общий случай: Что если ua примерно равно vb, где u/v несократимая дробь?

[Deggial]

jivar в сообщении #710019 писал(а):

Что если ua примерно равно vb, где u/v несократимая дробь?

замечание за неоформление формул $\TeX$ом

jivar в сообщении #710005 писал(а):

$x=integerpart(sqrt(n)), y=x^2 - n$

$x=[\sqrt{n}]$

[jivar]

Имеется ввиду, что если, например а близко к 2б, то можно увеличить стартовое значение х в переборе?

[jivar]

Разобрался. Удаляйте тему.