Integer factorization: Difference between revisions

Revision as of 03:06, 30 October 2003

Revision as of 00:39, 8 November 2003

Line 1:

[[de:Faktorisierung]] [[ja:素因数分解]]

In [[mathematics]], the '''integer prime-factorization''' (also known as '''prime decomposition''') problem is this: given a positive [[integer]], write it as a product of [[prime number]]s. For example, given the number 45, the prime factorization would be 3²·3·5. The factorization is always unique, according to the [[fundamental theorem of arithmetic]]. This problem is of significance in [[mathematics]], [[cryptography]], [[computational complexity theory|complexity theory]], and [[quantum computer|quantum computers]].

The complete list of factors can be derived from the prime factorization by incrementing the exponents from zero until the number is reached. For example, since 45 = 3²·5, 45 is divisible by 3⁰·5⁰, 3⁰·5¹, 3¹·5⁰, 3¹·5¹, 3²·5⁰, and 3²·5¹, or 1, 5, 3, 15, 9, and 45. In contrast, the prime factorization only includes prime factors.