MHB How Does Integer Factorization Impact Modern Cryptography and Beyond?

[matqkks]

Why is factorization of integers important? What are the real life applications of factorization? Are there are examples which have a real impact.

 

[Nono713]

If you had an efficient integer factorization algorithm you could do the following:
- efficiently extend all polynomial time algorithms modulo primes to composites via the CRT
- efficiently compute the order of the multiplicative group of integers modulo a composite (thereby breaking the most used public key encryption scheme in the world, namely RSA, and making millions of dollars)

Furthermore there is a good chance such an algorithm could be modified or extended to apply to other important and related classes of problems, such as the discrete logarithm problem, or be used to gain insight into e.g. the distribution of primes. It is unknown if such an algorithm even exists for classical computers, but integer factorization is known to be (theoretically) polynomial time on a sufficiently large quantum computer (Shor's algorithm).

Basically, it is important, because a lot of today's public key cryptography relies on the assumption that factorization is actually hard, an assumption which has been holding very well so far. A fast way to factorize would also have far-reaching consequences beyond this in more theoretical fields, as a lot of problems involving modular arithmetic basically need to factorize their input to work properly, which can be expensive in some cases if the modulus is of unknown provenance (though in many cases it doesn't matter as the modulus has a special form or its factorization is known in advance).