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:
“If one had to worry about one’s actions in respect of other people’s ideas, one might as well be buried alive in an antheap or married to an ambitious violinist. Whether that man is the prime minister, modifying his opinions to catch votes, or a bourgeois in terror lest some harmless act should be misunderstood and outrage some petty convention, that man is an inferior man and I do not want to have anything to do with him any more than I want to eat canned salmon.”
—Aleister Crowley (1875–1947)