Алгоритм Карацубы. Быстрое умножение.

Анатолий Карацуба

Для решения задач современной криптографии необходимы механизмы, реализующие математические операции с большими числами. Чем быстрее будут выполняться эти операции, тем лучше. В качестве курсовой работы по криптографии на 3-м курсе выбрал исследование алгоритма Карацубы. Самое страшное, что на то, чтобы отыскать "в чем фишка" ушло довольно длительное время поиска по просторам интернета... Потом написал код, провел некоторые сравнительные тесты... Но это все уже не так важно и интересно.

В данном топике изложу, как можно проще, суть метода быстрого умножения Карацубы и постараюсь объяснить, чем он лучше.

Для начала рассмотрим, как выполняется обычное умножение "столбиком". Пусть необходимо перемножить числа X и Y. Представим их в виде:

• X = aT + b
• Y = cT + d

T - можно рассматривать, как "отступ" от "конца" числа или величину сдвига (сколько нулей нужно добавить в конце числа). Т.е. если мы говорим о десятичной системе исчисления, то T - некоторая степень 10-ти. Для простоты возьмем двузначные числа:

• X = 12 = 10 + 2
• Y = 34 = 30 + 4

Умножение "в столбик" будет выглядеть следующим образом:

XY = (aT + b)(cT + d) = acT² + (ad + bc)T + bd

Таким образом мы выполняем 4 операции умножения. Для числе из нашего примера:

XY =  acT² + (ad + bc)T + bd = 1х3х10² + (1x4 + 2x3)x10 + 2x4 = 300 + 100 + 8 = 408

Теперь рассмотрим умножение методом Карацубы:

XY =  acT² + (ad + bc)T + bd = acT² + ((a+b)(c+d) - ac - bd)T + bd

Заметим, что выполняются три операции умножения, вместо четырех. Таким образом сложность вычислений снижается с N² до N^log(3). (Имеется ввиду двоичный логарифм).

Для чисел из примера:

XY =  acT² + ((a+b)(c+d) - ac - bd)T + bd = 1х3х10² +((1 + 2)(3 +4) - 1x3 - 2x4)x10 + 2x4 = 300 + (3x7 - 3 - 8)x10 + 8 = 300 + 100 + 8 = 408

Естественно, для числе малой разрядности метод Карацубы выглядит более громоздким и неудобным. Более того, для менее чем 32-разрядных (на 32-разрядной архитектуре) и менее 64-х разрядных (на 64-разрядной архитектуре) метод Карацубы, согласно моим опытам, проигрывает во времени умножению "в столбик". Но после этого порога наблюдается обратная тенденция. А с учетом того, что результаты разложения чисел, мы также можем перемножать методом Карацубы (до тех пор, пока их разрядность не опустится ниже разрядности архитектуры), то при переходе разрядности чисел в следующую степень двойки мы получаем скачок в разности скорости работы алгоритмов.

Понравилась статья? Нажми на кнопку и расскажи друзьям: