Content deleted Content added
No edit summary |
No edit summary |
||
Line 9:
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.
If a large, ''n''-[[bit]] number is the product of two primes that are roughly the same size, then no [[algorithm]] is known that can factor in polynomial time. That means there is no known algorithm that can factor it in time [[Big O notation|O]](''n''<sup>''k''</sup>) for any constant ''k''. There are algorithms, however, that are faster than [[Big O notation|Θ]](e<sup>''n''</sup>). In other words, the best known algorithms are sub-exponential, but super-polynomial. In particular, the best known asymptotic running time is for the [[general number field
:<math>
| |||