Алгоритмы быстрого умножения чисел

Скорость работы алгоритма RSA

Как при шифровании и расшифровывании, так и при создании и проверке подписи алгоритм RSA по существу состоит из возведения в степень, которое выполняется как ряд умножений.

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

Методы “быстрого умножения” (например, методы, основанные на быстром преобразовании Фурье (Fast Fourier Transform, FFT)) выполняются гораздо меньшим количеством шагов. Тем не менее, они не получили широкого распространения из-за сложности программной реализации, а также потому, что с распространенными размерами ключей они фактически работают медленнее. Однако производительность и эффективность приложений и оборудования, реализующих алгоритм RSA, быстро увеличиваются.

Алгоритм Карацубы — метод быстрого умножения со сложностью вычисления n^log₂³. В то время, как наивный алгоритм, умножение в столбик, требует n² операций. Следует заметить, что при длине чисел короче нескольких десятков знаков (точнее определяется экспериментально), быстрее работает обычное умножение.
Представим, что есть два числа A и B длиной n в какой-то системе счисления BASE:
A = a_n-1a_n-2...a₀
B = b_n-1a_n-2...a₀, где a_?, b_? — значение в соотв. разряде числа.
Каждое из них можно представить в виде суммы их двух частей, половинок длиной m = n / 2 (если n нечетное, то одна часть короче другой на один разряд:
A₀ = a_m-1a_m-2...a₀
A₁ = a_n-1a_n-2...a_m
A = A₀ + A₁ * BASE^m
B₀ = b_m-1b_m-2...b₀
B₁ = b_n-1b_n-2...b_m
B = B₀ + B₁ * BASE^m
Тогда: A * B = (A₀ + A₁ * BASE^m) * (B₀ + B₁ * BASE^m) = A₀ * B₀ + A₀ * B₁ * BASE^m + A₁ * B₀ * BASE^m + A₁ * B₁ * BASE^{2 * m} = A₀ * B₀ + (A₀ * B₁ + A₁ * B₀) * BASE^m + A₁ * B₁ * BASE^{2 * m}
Здесь нужно 4 операции умножения (части формулы * BASE^{? * m} не являются умножением, фактически указывая место записи результата, разряд). Но с другой стороны:
(A₀ + A₁) * (B₀ + B₁) = A₀ * B₀ + A₀ * B₁ + A₁ * B₀ + A₁ * B₁
Посмотрев на выделенные части в обоих формулах. После несложных преобразований количество операций умножения можно свести к 3-м, заменив два умножения на одно и несколько операций сложения и вычитания, время выполнения которых на порядок меньше:
A₀ * B₁ + A₁ * B₀ = (A₀ + A₁) * (B₀ + B₁) — A₀ * B₀ — A₁ * B₁
Окончательный вид выражения:
A * B = A₀ * B₀ + ((A₀ + A₁) * (B₀ + B₁) — A₀ * B₀ — A₁ * B₁) * BASE^m + A₁ * B₁ * BASE^{2 * m}
Графическое представление:

Пример
Для примера умножим два восьмизначных числа в десятичной системе 12345 и 98765:

Из изображении явно видна рекурсивная природа алгоритма. Для числа длиной менее четырех разрядов применялось наивное умножение.

Дата добавления: 2015-04-23