322
линейного в «a» пошагово, поочередно, по битам a иd b, начиная битами нижнего
порядка и вычисляя соответствующий выходной бит и «текущий бит» на каждом
шаге. (Подробности опущены). Умножение двух
n-битных целых чисел a и b, что-
бы использовать другой пример, можно сделать созданием списка n целых чисел
длиной не более 2n (каждое из которых равно a • 2i−1 • bi, где bi – i-й бит b) и
последующим сложением этих n целых чисел, чтобы получить конечный результат.
(Деление с
остатком,
сложнее для реализации, но также может быть выполнено).
Несмотря на то, что этих алгоритмов начальной школы достаточно, чтобы проде-
монстрировать, что вышеупомянутые проблемы могут быть решены в течение поли-
номиального времени, интересно отметить, что эти алгоритмы в некоторых случаях
– не самые лучшие из доступных. В качестве примера, простой алгоритм для умноже-
ния, приведенный выше, перемножает два n-битных числа за время O(n2), но суще-
ствует более хороший алгоритм, действующий в течение времени O(nlog23) (и даже
этот алгоритм, не является самым лучшим из возможных). В то время как,
разница
несущественна для такого размера чисел, с которыми мы сталкиваемся ежедневно,
она становится
заметной, когда числа большие. В криптографических приложениях
нередко используются целые числа, длиной тысячи битов (т.е., n > 1000) и разумный
выбор
используемых алгоритмов, становится критическим.
Достарыңызбен бөлісу: