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

Question

Пропуск деталей методов для вычисления простых чисел и методов факторизации.

Зачем заниматься факторингом?

Каковы его приложения?

Answer 1

Вау, так много ссор в этой теме.

По иронии судьбы, этот вопрос имеет серьезный правильный ответ.

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

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

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

Answer 2

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

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

Answer 3

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

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

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