Euler's factorization method


Euler's factorization method

Euler's factorization method is a method of factorization based upon representing a positive integer N as the sum of two squares in "two different ways":

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

Although the algebraic factorization of binomial numbers cannot factor sums of two squares (indeed a number expressive in "one" way as the sum of two squares is a prime) if one can find two "distinct" representations of a number as sums of two squares it leads as follows to a factorization:

From N = a^2 + b^2 = c^2 + d^2 (2)

we get by subtracting c^2 and b^2 from both sides to create a difference of two squares:a^2 - c^2 = d^2 - b^2 (3)

and then it follows that:

(a - c)cdot(a + c) = (d - b)cdot(d + b) (4)

By convention, d and b are either both odd or both even, so that their difference will be even. Now we define a constant k as the greatest common factor of (a - c) and (d - b) so that:

(a - c) = kl and (d - b) = km GCD (l, m) = 1 so that, after substituting into (4):

lcdot(a + c) = mcdot(d + b) (5)

Because l and m are relatively prime, we must have (a + c) divisible by m, which thus gives:

(a + c) = mn (6) and;(d + b) = ln (7)

The resultant factorization of the original number N can be shown to be equal to:

N = [(frac{k}{2})^2 + (frac{n}{2})^2] cdot(m^2 + l^2)

History and applications

The idea that two distinct representations of an odd positive integer may lead to a factorization was apparently first proposed by Marin Mersenne. However, it was not put to use extensively until Euler one hundred years later. His most celebrated use of the method that now bears his name was to factor the number N = 1000009, which apparently was previously thought to be prime even though it is not a pseudoprime by any major primality test.

Since:

1000009 = 1000^2 + 3^2 = 972^2 + 235 ^2

we have from the formulae above:

Thus,

1000009 = [(frac{4}{2})^2 + (frac{34}{2})^2] cdot(58^2 + 7^2)
* = (2^2 + 17^2)cdot(58^2 + 7^2)
* = (4 + 289)cdot(3364 + 49)
* = 293cdot3413

Euler's factorization method is more effective than Fermat's for integers whose factors are not close together and potentially much more efficient than trial division if one can find representations of numbers as sums of two squares reasonably easily. Euler's development ultimately permitted much more efficient factoring of numbers and, by the 1910s, the development of large factor table going up to about ten million. The methods used to find representations of numbers as sums of two squares are essentially the same as with finding differences of squares in Fermat's factorization method.

The great disadvantage of Euler's factorization method is that it cannot be applied to factoring an integer with any prime factor of the form 4"k"+3 occurring to an odd power in its prime factorization, as such a number can never be the sum of two squares. Even odd composite numbers of the form 4"k"+1 are often the product of two primes of the form 4"k"+3 (e.g. 3053 = 43 × 71) and again cannot be factored by Euler's method.

This restricted applicability has made Euler's factorization method disfavoured for computer factoring algorithms, since any user attempting to factor a random integer is unlikely to know whether Euler's method can actually be applied to the integer in question. It is only relatively recently that there have been attempts to develop Euler's method into computer algorithms for use on specialised numbers where it is known Euler's method can be applied.

References

* "Euler's Factorization Method"; in Ore, Oystein; "Number Theory and Its History"; pp. 59-64. ISBN 0486656209

* McKee, James; "Turning Euler's Factoring Method into a Factoring Algorithm"; in "Bulletin of the London Mathematical Society" 1996; issue 28 (volume 4); pp. 351-355


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Dixon's factorization method — In number theory, Dixon s factorization method (also Dixon s random squares method[1] or Dixon s algorithm) is a general purpose integer factorization algorithm; it is the prototypical factor base method, and the only factor base method for which …   Wikipedia

  • Integer factorization — In number theory, integer factorization is the way of breaking down a composite number into smaller non trivial divisors, which when multiplied together equal the original integer.When the numbers are very large, no efficient integer… …   Wikipedia

  • Método de factorización de Euler — El método de factorización de Euler es un método de factorización basado en la representación de un entero positivo N como la suma de dos cuadrados de dos maneras distintas: N = a2 + b2 = c2 + d2 Aunque la factorización algebraica de números… …   Wikipedia Español

  • Continued fraction factorization — In number theory, the continued fraction factorization method (CFRAC) is an integer factorization algorithm. It is a general purpose algorithm, meaning that it is suitable for factoring any integer n, not depending on special form or properties.… …   Wikipedia

  • Chakravala method — The chakravala method (Hindi: चक्रवाल विधि) is a cyclic algorithm to solve indeterminate quadratic equations, including Pell s equation. It is commonly attributed to Bhāskara II, (c. 1114 – 1185 CE)[1][2] although some attribute it to Jayadeva (c …   Wikipedia

  • Finite element method — The finite element method (FEM) (sometimes referred to as finite element analysis) is a numerical technique for finding approximate solutions of partial differential equations (PDE) as well as of integral equations. The solution approach is based …   Wikipedia

  • List of mathematics articles (E) — NOTOC E E₇ E (mathematical constant) E function E₈ lattice E₈ manifold E∞ operad E7½ E8 investigation tool Earley parser Early stopping Earnshaw s theorem Earth mover s distance East Journal on Approximations Eastern Arabic numerals Easton s… …   Wikipedia

  • List of numerical analysis topics — This is a list of numerical analysis topics, by Wikipedia page. Contents 1 General 2 Error 3 Elementary and special functions 4 Numerical linear algebra …   Wikipedia

  • Quadratic sieve — The quadratic sieve algorithm (QS) is a modern integer factorization algorithm and, in practice, the second fastest method known (after the general number field sieve). It is still the fastest for integers under 100 decimal digits or so, and is… …   Wikipedia

  • Numerical analysis — Babylonian clay tablet BC 7289 (c. 1800–1600 BC) with annotations. The approximation of the square root of 2 is four sexagesimal figures, which is about six decimal figures. 1 + 24/60 + 51/602 + 10/603 = 1.41421296...[1] Numerical analysis is the …   Wikipedia