Prime Decomposition
By the fundamental theorem of arithmetic, every positive integer has a unique prime factorization. (A special case for 1 is not needed using an appropriate notion of the empty product.) However, the fundamental theorem of arithmetic gives no insight into how to obtain an integer's prime factorization; it only guarantees its existence.
Given a general algorithm for integer factorization, one can factor any integer down to its constituent prime factors by repeated application of this algorithm. However, this is not the case with a special-purpose factorization algorithm, since it may not apply to the smaller factors that occur during decomposition, or may execute very slowly on these values. For example, if N is the number (2521 − 1) × (2607 − 1), then trial division will quickly factor 10N as 2 × 5 × N, but will not quickly factor N into its factors.
Read more about this topic: Integer Factorization
Famous quotes containing the word prime:
“Vanessa wanted to be a ballerina. Dad had such hopes for her.... Corin was the academically brilliant one, and a fencer of Olympic standard. Everything was expected of them, and they fulfilled all expectations. But I was the one of whom nothing was expected. I remember a game the three of us played. Vanessa was the President of the United States, Corin was the British Prime Minister—and I was the royal dog.”
—Lynn Redgrave (b. 1943)