The *prime factorization* is a unique way to write a number as a product of [[Prime Number|prime numbers]]. Let's consider an example: the number $15$ can be written as $15=3 \times 5$ Both numbers, $3$ and $5$ are [[Prime Number|prime number]], i.e. they are only divisible by $1$ and themselves. In other words, their *prime factorization* has exactly two terms ($3=1\times 3$). ![[prime_factorization.excalidraw.light.svg]] While it is quite easy to compute the product of all factors on the right side (every calculator can easily do that), computing the factorization is hard. It is actually so hard that it is used as a [[Trapdoor function|trapdoor function]] in encryption. >[!read]- Further Reading >- [[Trapdoor function]] >- [[Prime Number]] >- [[Rivest-Shamir-Adleman Algorithm|RSA algorithm]] >- [[Encryption]] >[!ref]- References