Калькулятор факторизації Ферма

Про цей калькулятор

Метод факторизації Ферма спирається на те, що будь-яке непарне ціле число N можна записати як різницю двох квадратів: N = a² − b² = (a−b)(a+b). Алгоритм починає з a = ⌈√N⌉ і на кожному кроці збільшує a на 1, перевіряючи, чи a² − N саме є повним квадратом (b²); щойно це так, N одразу розкладається на (a−b)(a+b). Цей калькулятор виконує такий цикл і показує кожен крок, зроблений для пошуку множників.

Метод збігається за дуже малу кількість кроків, коли два множники числа N близькі один до одного, — його головна слабкість є водночас його найважливішим застосуванням у реальному житті: студенти-криптографи та дослідники безпеки використовують факторизацію Ферма, щоб показати, чому модулі RSA треба будувати з простих чисел, які далеко відстоять одне від одного, адже прості числа, обрані надто близько, роблять модуль тривіально зламуваним. Це також стандартна вправа курсів з теорії чисел для ілюстрації міркувань про різницю квадратів.