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 can be written as or as and Euler's method gives the factorization .
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 one hundred years later by Euler. His most celebrated use of the method that now bears his name was to factor the number , which apparently was previously thought to be prime even though it is not a pseudoprime by any major primality test.
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. 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.
Disadvantage and limitation
[edit]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 4k + 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 4k + 1 are often the product of two primes of the form 4k + 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.
Theoretical basis
[edit]The Brahmagupta–Fibonacci identity states that the product of two sums of two squares is a sum of two squares. Euler's method relies on this theorem but it can be viewed as the converse, given we find as a product of sums of two squares.
First deduce that
and factor both sides to get
- (1)
Now let and so that there exists some constants satisfying
- ,
- ,
- ,
- ,
Substituting these into equation (1) gives
Canceling common factors yields
Now using the fact that and are pairs of relatively prime numbers, we find that
So
We now see that and
Applying the Brahmagupta–Fibonacci identity we get
As each factor is a sum of two squares, one of these must contain both even numbers: either or . Without loss of generality, assume that pair is even. The factorization then becomes
Worked example
[edit]Since:
we have from the formula above:
a = 1000 | (A) a − c = 28 | k = gcd[A,C] = 4 |
b = 3 | (B) a + c = 1972 | h = gcd[B,D] = 34 |
c = 972 | (C) d − b = 232 | l = gcd[A,D] = 14 |
d = 235 | (D) d + b = 238 | m = gcd[B,C] = 116 |
Thus,
Pseudocode
[edit]function Euler_factorize(int n) -> list[int] if is_prime(n) then print("Number is not factorable") exit function for-loop from a=1 to a=ceiling(sqrt(n)) b2 = n - a*a b = floor(sqrt(b2)) if b*b==b2 break loop preserving a,b if a*a+b*b!=n then print("Failed to find any expression for n as sum of squares") exit function for-loop from c=a+1 to c=ceiling(sqrt(n)) d2 = n - c*c d = floor(sqrt(d2)) if d*d==d2 then break loop preserving c,d if c*c+d*d!=n then print("Failed to find a second expression for n as sum of squares") exit function A = c-a, B = c+a C = b-d, D = b+d k = GCD(A,C)//2, h = GCD(B,D)//2 l = GCD(A,D)//2, m = GCD(B,C)//2 factor1 = k*k + h*h factor2 = l*l + m*m return list[ factor1, factor2 ]
References
[edit]- Ore, Oystein (1988). "Euler's Factorization Method". Number Theory and Its History. Courier Corporation. pp. 59–64. ISBN 978-0-486-65620-5.
- McKee, James (1996). "Turning Euler's Factoring Method into a Factoring Algorithm". Bulletin of the London Mathematical Society. 4 (28): 351–355. doi:10.1112/blms/28.4.351.
Well, that’s interesting to know that Psilotum nudum are known as whisk ferns. Psilotum nudum is the commoner species of the two. While the P. flaccidum is a rare species and is found in the tropical islands. Both the species are usually epiphytic in habit and grow upon tree ferns. These species may also be terrestrial and grow in humus or in the crevices of the rocks.
View the detailed Guide of Psilotum nudum: Detailed Study Of Psilotum Nudum (Whisk Fern), Classification, Anatomy, Reproduction