Integer factorization: Difference between revisions

Revision as of 14:20, 18 May 2003

Revision as of 20:07, 19 June 2003

Line 1:

[[de:Faktorisierung]]

In [[mathematics]], the '''Integerinteger 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 answerprime factorization would be 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.

Given two large prime numbers, it is easy to multiply them together. However, given their product, it appears to be difficult to find the factors. This is relevant for many modern systems in [[cryptography]]. If a fast method were found for solving the integer factorization problem, then several important cryptographic systems would be broken, including the [[RSA]] public-key algorithm, and the [[Blum Blum Shub]] random number generator.