В чем заключается метод Эйлера для разложения больших чисел на простые множители?

Метод Эйлера для разложения больших чисел на простые множители заключается в том, чтобы записать число в виде суммы двух квадратов двумя разными путями. ru.wikipedia.org

Например, число 1000009 можно записать как 1000² + 3² или как 972² + 235², и тогда метод Эйлера даёт разложение 1000009 = 293 ⋅ 3413. en.wikipedia.org ru.wikipedia.org

Этот метод эффективен для целых чисел, множители которых не близки друг к другу, и потенциально намного эффективнее пробного деления, если можно достаточно легко найти представления чисел в виде суммы двух квадратов. en.wikipedia.org

Однако у метода есть ограничение: он не может быть применён к разложению на множители целого числа с любым простым множителем вида 4k + 3, имеющим нечётную степень, поскольку такое число никогда не может быть суммой двух квадратов. en.wikipedia.org