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

Об этом калькуляторе

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

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