TOPICS

Euler's Factorization Method

A factorization algorithm which works by expressing N as a quadratic form in two different ways. Then

N=a^2+b^2=c^2+d^2,
(1)

so

a^2-c^2=d^2-b^2
(2)
(a-c)(a+c)=(d-b)(d+b).
(3)

Let k be the greatest common divisor of a-c and d-b so

a-c=kl
(4)
d-b=km
(5)
(l,m)=1,
(6)

(where (l,m) denotes the greatest common divisor of l and m), and

l(a+c)=m(d+b).
(7)

But since (l,m)=1, m|a+c and

a+c=mn,
(8)

which gives

b+d=ln,
(9)

so we have

[(1/2k)^2+(1/2n)^2](l^2+m^2)=1/4(k^2+n^2)(l^2+m^2)
(10)
=1/4[(km)^2+(kl)^2+(nm)^2+(nl)^2]
(11)
=1/4[(d-b)^2+(a-c)^2+(a+c)^2+(d+b)^2]
(12)
=1/4(2a^2+2b^2+2c^2+2d^2)
(13)
=1/4(2N+2N)
(14)
=N.
(15)

See also

Prime Factorization Algorithms

Explore with Wolfram|Alpha

Cite this as:

Weisstein, Eric W. "Euler's Factorization Method." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/EulersFactorizationMethod.html

Subject classifications