Введение в современную криптографию
жүктеу/скачать 6.4 Mb. Pdf көрінісі
|
| Целочисленная арифметика
Основные операции Мы начнем наше объяснение алгоритмической теории чисел с обсуждения сло- жения/вычитания, умножения и деления с остатком целых чисел. Небольшое раз- мышление показывает, что все эти операции могут быть выполнены в течение по- линомиального времени в длине входных данных, с использованием для этих задач стандартных алгоритмов «начальной школы». Например, сложение двух положи- тельных целых чисел a и b, при a > b может быть выполнено в течение времени, 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) и разумный выбор используемых алгоритмов, становится критическим. жүктеу/скачать 6.4 Mb. Достарыңызбен бөлісу:
|