Составители:
ПРИЛОЖЕНИЯ
ЭЛЕМЕНТЫ ТЕОРИИ ЧИСЕЛ
Как известно [4, 9], целые числа по модулю n с использованием
операций сложения и умножения образуют коммутативное кольцо
при соблюдении требований ассоциативности, коммутативности и
дистрибутивности.
Поскольку приведение по модулю n является гомоморфным
отображением из кольца целых в кольцо целых по модулю n, то
можно либо сначала приводить
по модулю n, а затем выполнять
операции, либо сначала выполнять операции, а затем приводить по
модулю n:
(a ± b) mod n = [a(mod n) ± b(mod n)] mod n,
(a ⋅ b) mod n = [a(mod n) ⋅ b(mod n)] mod n,
[a ⋅ (b + c)] mod n = {[a ⋅b(mod n)] + [a⋅ c(mod n)]} mod n.
В криптографии [1, 22, 23] используется множество вычислений
по модулю n, например вычисления дискретных логарифмов и
квадратных корней. Это связано с тем, что с вычислениями по
модулю удобнее работать, потому что они ограничивают диапазон
всех вычислений промежуточных величин и результата.
Например, промежуточные результаты операции сложения,
вычитания или умножения по модулю n длиной
k бит будут не
длиннее 2k бит, а вычисление степени числа a по модулю n
a
x
mod n
можно выполнить как ряд умножений и делений. В силу
дистрибутивности этих операций удобнее и быстрее произвести
возведение в степень как ряд последовательных умножений, выполняя
каждый раз приведение по модулю.
Так, например [17], если нужно вычислить a
16
mod n, не следует
применять примитивный подход с выполнением 15 перемножений и
одного приведения по модулю большого числа:
153
Страницы
- « первая
- ‹ предыдущая
- …
- 149
- 150
- 151
- 152
- 153
- …
- следующая ›
- последняя »
