В криптографии факторизацией называют разложение числа на простые множители. На предположении о вычисления сложности данного процесса основывается криптостойкость некоторых алгоритмов шифрования с открытым ключом, таких, как RSA, алгоритм на эллиптических кривых. Существует большое количество методов факторизации, которые отличаются вычислительной сложностью.

Вопрос о существовании алгоритма факторизации с полиномиальной сложностью на классическом компьютере является одной из важных открытых проблем современной теории чисел. В то же время доказано, что родственная задача о распознавании простоты числа является полиномиально разрешимой и для неё существует много эффективных тестов простоты.

Эти методы могут быть использованы в алгоритмах шифрования RSA, где вся секретная часть спрятана не в знании кода алгоритма, а в наличии ключа, длинного числа, подданного на «вход» алгоритма вместе с защищаемыми данными. Читать дальше >