Euler's factorization method

Euler's factorization method is a technique for factoring a number by writing it as a sum of two squares in two different ways. For example the number 1000009 {\displaystyle 1000009} can be written as 1000 2 + 3 2 {\displaystyle 1000^{2}+3^{2}} or as 972 2 + 235 2 {\displaystyle 972^{2}+235^{2}} and Euler's method gives the factorization 1000009 = 293 ⋅ 3413 {\displaystyle 1000009=293\cdot 3413} .

Source: Wikipedia — Euler's factorization method (CC BY-SA 4.0)