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

Question

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

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

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

Answer 1

Ого, столько сражений в этой теме.

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

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

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

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

Answer 2

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

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

Answer 3

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

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

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