Математика: Факторизация

Ух ты, сколько драк в этой ветке.

По иронии судьбы, на этот вопрос ЕСТЬ важный правильный ответ.

Факторизация настолько широко используется в алгоритмах шифрования/дешифрования, что RSA регулярно проводит соревнования, задача которых состоит в том, чтобы разложить на множители определенные большие числа, кратные очень большим простым числам.

Это, в свою очередь, связано с тем, что несколько алгоритмов шифрования/дешифрования основаны на предположении, что факторизация занимает очень много времени, что (предположительно) делает трудным и/или непрактичным взлом определенных алгоритмов шифрования/дешифрования, учитывая предположение, что хакер/ взломщик не имеет доступа к открытым/закрытым ключам.

Затем можно использовать алгоритмы факторизации для проверки того, насколько сильным является тот или иной алгоритм шифрования/дешифрования.

Асимметричное шифрование, такое как RSA/DAS, основано на том факте, что факторизация — очень сложная вещь. Если я дам вам число, которое при печати будет размером с целую газетную страницу, и скажу вам: «Это число было получено путем умножения двух простых чисел. Теперь, пожалуйста, разложите его на множители»… вы думаете, что сможете? Поверьте мне, любой известный способ сделать это займет целую вечность. Не существует эффективного способа сделать это без использования тонн процессорного времени (столетий) или тонн памяти (больше памяти, чем все интернет-серверы в мире вместе взятые). Если вы найдете простой способ факторизовать такие большие числа, вы нарушите, например, подпись электронной почты и SSL (HTTPS).

Однако существуют и другие задачи, связанные с факторизацией. Факторизация касается не только числа. Иногда речь идет о том, «почему многочлены являются множителями других многочленов». Так могут математические задачи зависеть от факторизации, и так много проблем может быть решено с ее помощью. Таким образом, эффективная факторизация имеет большое значение. Даже матрицы можно разложить на множители.

Его можно использовать для взлома некоторых типов шифрования (если ключ достаточно мал).

Вам также понадобится это для некоторых типов научного программного обеспечения.

Еще одно приложение — отвечать на вопросы ProjectEuler.