Проблемы факторизации чисел и дискретного логарифмирования

Еще в младших классах школы все решают задачи по разложению чисел на простые множители. Делается это просто делением данного числа на последовательные простые числа. Если число большое, то этот алгоритм будет работать долго (даже на компьютере). Если же число очень большое (скажем, состоит из 200 знаков), самому современному компьютеру могут понадобиться годы работы. И, как это ни странно, до сих пор математики не придумали никакого другого алгоритма, работающего существенно быстрее. Проблема построения такого алгоритма называется проблемой факторизации чисел. С другой стороны, существуют быстрые алгоритмы, позволяющие с большой вероятностью определять, является ли данное число простым или нет (но никакого разложения числа на простые множители эти алгоритмы не находят).

Криптографические приложения проблемы факторизации чисел и, особенно, заинтересованность пользователей банковских систем цифровой подписи привели к резкому увеличению исследований, связанных с разложением чисел на множители. В последние годы благодаря применению тонких методов теории чисел и алгебраической геометрии было разработано несколько эффективных алгоритмов факторизации. Наилучший из таких алгоритмов еще не является полиномиальным, но уже и не экспоненциальный, он относится к классу так называемых субэкспоненциальных алгоритмов (говоря строго, его сложность превосходит любой полином от n, но меньше, чем 2 ^N , где N = n ^ε для любого ε >0).

Среди последних достижений в этой области можно упомянуть об успехе Ленстры и Монасси, разложивших в июне 1990 года 155‑разрядное число на три простых. Для этого они использовали 1000 объединенных ЭВМ и шесть недель их машинного времени. Вычисления проводились с помощью алгоритма английского математика Дж. Полларда. Ленстра и Монасси считают, что в настоящее время (1991 г.) можно в течение года разложить новые классы целых чисел длиной до 155 разрядов, затратив на это $200 млн.

Еще одна большая проблема – дискретное логарифмирование в конечных полях. Пусть, например, нам даны элементы a и b из конечного поля F, причем известно, что a = b ^x при некотором натуральном x. Задача дискретного логарифмирования состоит в том, чтобы определить это x. Можно, разумеется, просто перебирать последовательно все натуральные числа, проверяя, выполнено ли указанное равенство, но это будет экспоненциальный алгоритм. Пока наилучший из разработанных математиками алгоритмов дискретного логарифмирования является субэкспоненциальным.

В настоящее время эти описанные трудные математические проблемы имеют многочисленные криптографические приложения (см. этюды 3.5, 3.6, 3.7).