Integer factorization: Difference between revisions

Revision as of 02:28, 2 January 2004

Revision as of 08:44, 7 January 2004

Line 6:

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.

Although fast factoring is ''one'' way to break these systems, there may be ''other'' ways to break them that don't involve factoring. So it is possible that the integer factorization problem is truly hard, yet these systems can still be broken quickly. A rare exception is the Blum Blum Shub generator. It has been proved to be exactly as hard as integer factorization. There is no way to break it without also solving integer factorization quickly.