Факторизация Ферма
Данный калькулятор позволяет факторизовать (разложить на множители) нечетное натуральное число n. Пользоваться им крайне просто:
Инструкция:
Вводим в поле нечетное натуральное число Жмем на кнопку «Факторизовать число» Получаем решение и ответ.
Ограничения:
Максимальное число для факторизации — 100 000 000. Так как алгоритм факторизации Ферма работает достаточно медленно в случае, если разница между множителями велика. Именно по этой причине простые числа раскладываются на множители медленнее остальных. Максимальное простое число для ввода не превышает 50 000 000. Причина указана в пункте 1. Вводить необходимо только нечетные и только натуральные числа.
Вопросы и ответы:
Вопрос. Что такое пропущенные итерации?
Ответ: Так как в ходе работы алгоритма выполняются тысячи операций, выводить всё решение на страницу нецелесообразно, именно поэтому в решении пропускается вывод большинства итераций алгоритма, которые не несут смысловой нагрузки.
Изучаем алгоритм, который эффективен, когда у $$n$$ есть делитель (не обязательно простой), незначительно превосходящий $$\sqrt{n}.$$ Идею алгоритма придумал Ферма.
Предположим для начала, что $$n$$ нечетное. Если бы оно было четным, то 2 было бы его делителем. Ключевая идея алгоритма состоит в том, чтобы попробовать представить $$n$$ в виде $$n = x^2$$ — $$y^2$$, где $$x, y$$ — неотрицательные целые числа. Если такие числа найдены, то
$$n = x^2$$ — $$y^2 = (x $$ — $$y) * (x + y).$$
Значит, $$x$$ — $$y$$ и $$x + y$$ являются делителями числа $$n.$$
Алгоритм Ферма разложения на множители
Ввод: нечетное натуральное число $$n.$$
Вывод: множитель числа $$n$$ или сообщение о том, что $$n$$ простое.
Шаг 1. Положить $$x = [\sqrt{n}].$$ Если $$n = x^2$$ то $$x$$ является делителем числа $$n$$ и работа алгоритма останавливается; в противном случае увеличить $$x$$ на 1 и перейти к шагу 2.
Шаг 2. Если $$x = \frac{n+1}{2}$$ то число $$n$$ простое, и работа алгоритма останавливается; в противном случае вычислить $$y = \sqrt{x^2\ –\ n}.$$
Шаг 3. Если число $$y$$ целое (т. е., если $$[y^2] = x^2$$ — $$n$$), то $$n$$ раскладывается в произведение $$(x $$ — $$y) * (x + y)$$ и работа алгоритма останавливается; в противном случае увеличить $$x$$ на 1 и перейти к шагу 2.
Сложность алгорита: $$O(n)$$ или $$O(exp(N))$$
Как показывает следующий пример, этот алгоритм очень прост в применении. Допустим, мы хотим разложить на множители число $$n = 1 342 127.$$ Сначала переменной $$x$$ присваивается целая часть числа $$n.$$ В примере она равна $$x = 1158.$$ Однако
$$x^2 = 1158^2 = 1 340 964 < 1 342 127.$$
Поэтому мы должны увеличить $$x$$ на 1. Мы продолжим этот процесс до тех пор, пока число $$\sqrt{x^2\ –\ n}.$$ не станет целым или не будет выполняться равенство $$x = \frac{n+1}{2}.$$ Заметим, что в нашем примере $$\frac{n+1}{2} = 671064.$$ Значения переменных $$x$$ и $$y$$ после завершения каждого цикла приведены в таблице.
Таким образом, на шестом цикле мы получили целое число. Значит, искомые числа $$x = 1164$$ и $$y = 113.$$ Соответствующие множители равны
$$x + y = 1277$$ и $$x$$ — $$y = 1051$$
Заметили неточность в работе калькулятора? Убедительная просьба сообщить об этом в комментариях или через