Факторизация (также называемая факторизацией и факторингом) - это разделение составного числа на числа, которые умножаются вместе, чтобы получить исходное число. Эти меньшие числа называются факторами или делителями. 1 является фактором всех чисел.
Прайм-факторизация - это разбиение составного числа на простые числа, которые можно перемножить, чтобы получить большее число. Обратите внимание, что поскольку 1 не является простым числом, оно не включается в простую факторизацию.
Например, 12 можно разложить как 4 × 3. Поскольку 4 не является простым числом, это не его простая факторизация. Факторизация простого числа 12 на самом деле 3 × 2 × 2.
Числа, которые получаются в результате факторизации, обычно упорядочиваются, например, начиная с наименьшего числа. Например, 72=2^3*3^2. Факторизация каждого числа уникальна. Это обобщается на:
- Каждое число имеет уникальную простую факторизацию
- Каждой простой факторизации соответствует уникальное число
Поскольку для больших чисел найти числа, которые нужно перемножить вместе, очень сложно, этот факт можно использовать в криптографии.
