Math: Factorisation

Question

Omitting details of methods to calculate primes, and methods of factorisation.

Why bother to factorise ?

What are its applications ?

Answer 1

Wow, so much fighting in this thread.

Ironically, this question HAS a major valid answer.

Factorization is actually used heavily in encryption/decryption algorithms, so much so that the RSA regularly conducts competitions wherein the task is to factorize certain large numbers that are multiples of very large prime numbers.

This is, in turn, because several encryption/decryption algorithms are based on the premise that factorization takes a very long time, which (supposedly) makes it difficult and/or impractical to crack certain encryption/decryption algorithms given the assumption that the hacker/cracker does not have access to public/private keys.

Factorization algorithms can then be used to verify just how strong any given encryption/decryption algorithm is.

Answer 2

Asymetric encryption as RSA/DAS bases on the fact, that factorization is a very hard thing. If I give you a number, that when printed out is as large as a whole newspaper page and tell you "This number has been generated by multiplying two prime numbers. Now please factorize it"... do you think you can? Trust me, any known way to do this will take an eternity. There is no effective way of doing it without either needing tons of CPU time (centuries) or tons of memory (more storage than all Internet servers on the world have together). If you find an easy way to factorize numbers that large, you break e-mail signing and SSL (HTTPS) for example.

However, there are other tasks related to factorization. Factorization is not only about number. Sometimes it's about "why polynomials are factors of another polynomials". So may mathematical tasks depend on factorization and so many problems can be solved by it. Thus effective factorization is of great value. Even matrices can be factorized.

Answer 3

It can be used to crack some types of encryption (if they key was small enough).

You would also need it for some types of scientific software.

One more application is to answer ProjectEuler Questions.