Факторизация числа методом Ферма

Факторизация Ферма

❓Инструкция

📘 Данный калькулятор позволяет факторизовать (разложить на множители) нечетное натуральное число 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$$

ℹ Заметили неточность в работе калькулятора? Убедительная просьба сообщить об этом в комментариях или через форму обратной связи. Заранее Вас благодарим.

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *