Euler's Factorization Method
Works by expressing
as a
Quadratic Form
in two different ways. Then
(1)
so
(2)
(3)
Let
be the
Greatest Common Divisor
of
and
so
(4)
(5)
(6)
(where
denotes the
Greatest Common Divisor
of
and
), and
(7)
But since
,
and
(8)
which gives
(9)
so we have
(
10
)
See also
Prime Factorization Algorithms
© 1996-9
Eric W. Weisstein
1999-05-25