Оптимизация метода Монтгомери за счет использования однословных умножений по однословному модулю
Рассматривается операция умножения по модулю, от быстродействия которой в основном зависит быстродействие ассиметричной криптографии. Предлагается оптимизация метода Монтгомери нахождения остатка. Показано, что умножение n-разрядных чисел по n-разрядному модулю можно привести к однословным умножения...
Saved in:
| Published in: | Компьютерная математика |
|---|---|
| Date: | 2010 |
| Main Author: | |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2010
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/84570 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Оптимизация метода Монтгомери за счет использования однословных умножений по однословному модулю / А.Н. Терещенко // Компьютерная математика: сб. науч. тр. — 2010. — № 1. — С. 73-82. — Бібліогр.: 4 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860237453941538816 |
|---|---|
| author | Терещенко, А.Н. |
| author_facet | Терещенко, А.Н. |
| citation_txt | Оптимизация метода Монтгомери за счет использования однословных умножений по однословному модулю / А.Н. Терещенко // Компьютерная математика: сб. науч. тр. — 2010. — № 1. — С. 73-82. — Бібліогр.: 4 назв. — рос. |
| collection | DSpace DC |
| container_title | Компьютерная математика |
| description | Рассматривается операция умножения по модулю, от быстродействия которой в основном зависит быстродействие ассиметричной криптографии. Предлагается оптимизация метода Монтгомери нахождения остатка. Показано, что умножение n-разрядных чисел по n-разрядному модулю можно привести к однословным умножениям по однословному модулю.
Розглядається оптимізація множення за модулем, від часу виконання якої в основному залежить швидкодія асиметричної криптографії. Пропонується оптимізація методу Монтгомері обчислення лишку. Показано, що множення n-розрядних чисел за n-розрядним модулем можна привести до однослівних множень за однослівним модулем.
A modular multiplication that has a considerable influence on asymmetric cryptography performance is considered. An optimization of Montgomery's method of modulo calculation is proposed. It is shown that n-dimensional multiplication modulo n can yield a single precision multiplication by single precision module.
|
| first_indexed | 2025-12-07T18:25:18Z |
| format | Article |
| fulltext |
Компьютерная математика. 2010, № 1 73
Îïòèìèçàöèÿ
âû÷èñëåíèé
Рассматривается операция умно-
жения по модулю, от быстродей-
ствия которой в основном зави-
сит быстродействие ассимет-
ричной криптографии. Предлага-
ется оптимизация метода Монт-
гомери нахождения остатка.
Показано, что умножение n-раз-
рядных чисел по n-разрядному
модулю можно привести к одно-
словным умножениям по одно-
словному модулю.
А.Н. Терещенко, 2010
ÓÄÊ 681.511:3
À.Í. ÒÅÐÅÙÅÍÊÎ
ÎÏÒÈÌÈÇÀÖÈß ÌÅÒÎÄÀ
ÌÎÍÒÃÎÌÅÐÈ
ÇÀ Ñ×ÅÒ ÈÑÏÎËÜÇÎÂÀÍÈß
ÎÄÍÎÑËÎÂÍÛÕ ÓÌÍÎÆÅÍÈÉ
ÏÎ ÎÄÍÎÑËÎÂÍÎÌÓ ÌÎÄÓËÞ
Введение. При реализации криптографиче-
ских схем защиты информации, которые ос-
нованы на использовании односторонних и
односторонних с лазейкой функций, основ-
ная вычислительная нагрузка падает на вы-
полнение модулярных арифметических опе-
раций над большими числами. В связи с этим
последнее время значительное внимание
уделяется поиску вычислительно эффектив-
ных алгоритмов, которые выполняют опера-
ции модулярной арифметики [1 – 3].
Общее описание метода Монтгомери
В 1985 году П. Монтгомери (P. Montgo-
mery) предложил эффективный алгоритм [4]
вычисления
N
VUR ⋅= , где R , U , V ,
N – битовые двоичные числа. Этот алго-
ритм особенно удобен при использовании на
универсальных компьютерах (сигнальных
процессорах или микропроцессорах), кото-
рые способны быстро выполнять арифмети-
ческие действия по модулю степени двойки.
Особенностью алгоритма Монтгомери явля-
ется то, что этот алгоритм позволяет вычис-
лить остаток R без выполнения деления на
N . Благодаря особенному представлению
остаточного класса по модулю N алгоритм
заменяет операцию деления на N делением
на степень двойки, которая легко реализуется
линейными сдвигами на компьютере. R и N
должны быть взаимно простыми числами.
А.Н. ТЕРЕЩЕНКО
Компьютерная математика. 2010, № 1 74
Опишем основную идею алгоритма Монтгомери вычисления остатка [2].
Пусть дано число NU < . Определим его N -остаток, как
N
MUU ⋅= . Легко
показать, что множество { }10 −<≤⋅ NIMI
N
– полная система остатков,
т. е. содержит все числа между 0 и 1−N . Поэтому существует взаимно одно-
значное соответствие между числами из области от 0 до 1−N и вышеуказан-
ным множеством. Алгоритм Монтгомери использует это свойство, используя
более быструю процедуру умножения для вычисления N-остатка умножения
двух целых чисел, у которых известны их N-остатки. Когда известны
N-остатки чисел U и V , умножение Монтгомери определяется как N-остаток
следующим образом:
1
N
R U V M −= ⋅ ⋅ ,
где 1−M такое, что 11 =⋅ −
N
MM .
Тогда R – N-остаток произведения
N
VUR ⋅= , так как
NNN
MVUMMVMUMVUR ⋅⋅=⋅⋅⋅⋅=⋅⋅= −− 11 .
Для описания алгоритма Монтгомери вычисления остатка, нам понадобится
величина 1−N , для которого выполняется соотношение 111 =⋅−⋅ −− NNMM .
Целые числа 1−M и 1−N вычисляются расширенным алгоритмом Эвклида.
Пошаговое описание алгоритма Монтгомери вычисления произведения
N
MVUR 1−⋅⋅= , где U и V – заданные числа выглядят таким образом:
Алгоритм 1. Функция MonPro(U ,V )
Шаг 1. VUT ⋅= .
Шаг 2.
M
NTS 1−⋅= .
Шаг 3. MSNTR )( ⋅+= .
Шаг 4. Если NR > , то NRR −= .
Важной особенностью алгоритма Монтгомери является то, что 2M γ= яв-
ляется степенью двойки, что позволяет заменить операции умножение по моду-
лю M и деление на M операцией быстрого линейного сдвига.
Лема 1. Если числа U и V n -разрядные, то количество операций одно-
словного умножения в алгоритме 1 можно выразить следующей априорной
оценкой: 2* 3)( nnC = .
Доказательство. В алгоритме 1 шаги 1, 2 и 3 содержат операцию умноже-
ния, каждая из которых имеет сложность 2n .
ОПТИМИЗАЦИЯ МЕТОДА МОНТГОМЕРИ ЗА СЧЕТ ИСПОЛЬЗОВАНИЯ ОДНОСЛОВНЫХ …
Компьютерная математика. 2010, № 1 75
Примечание 1. Сложность 2n имеет диагональный метод, который является
эффективным при умножении больших чисел, длина которых не превышает
90<n машинных слов.
Предлагается в методе Монтгомери использовать два дополнительных чис-
ла M и M ′ вместо одного: MMN ′<< . Введение второго дополнительного
числа M ′ дает возможность использовать китайскую теорему об остатках и,
как результат, привести s -словную операцию умножения по модулю к одно-
словным операциям умножения по модулю.
Теорема 1 [2]. Сравнения im
uU
i
= имеют единственное решение среди
классов остатков по модулю ∏
−
=
=
1
0
n
i
imM такому, что 1),( =ij mm , ji ≠ .
Доказательство. Сначала построим сложный модуль ∏
−
=
=
1
0
n
i
imM .
Потом запишем величины 00 mMM = , 11 mMM = , ..., 11 −− = nn mMM ,
где 1),( =ii mM , 1,0 −= ni взаимно простые между собой.
Поэтому можно найти число ih , развязывая равенство 1=⋅
imii Mh [4].
Теперь рассмотрим величину
Mnnn MhuMhuMhuU 111111000 ... −−− ⋅⋅++⋅⋅+⋅⋅= . (1)
Найдем остаток U по модулю 0m . Так как каждое из чисел 1M , 2M ,...,
1−nM делится на 0m , то 0
0
uU
m
= . Аналогично im
uU
i
= .
Поэтому U – решение заданной системы равенств. Легко убедиться, что
решение (1) – единственное (как класс остатков по модулю M ).
Лемма 2. Если модуль ∏
−
=
=
1
0
n
i
imM такой, что 1),( =ij mm , ji ≠ , и извест-
ны числа ih такие, что 1=⋅
imii Mh , ii mMM = , 1),( =ii mM , 1,0 −= ni ,
то для любого числа MU < справедлива следующая оценка:
( ) nmhu
n
i
imii
i
<⋅∑
−
=
1
0
, (2)
где im
uU
i
= , 1,0 −= ni .
Доказательство. Очевидно, что imii mhu
i
<⋅ , 1,0 −= ni . Умножая обе
части на iM , получаем следующее выражение:
( )
i
i i im
u h M M⋅ ⋅ < , 1,0 −= ni .
А.Н. ТЕРЕЩЕНКО
Компьютерная математика. 2010, № 1 76
Откуда вытекает, что сумма по i будет меньше, чем Mn ⋅
( ) MnMhu
n
i
imii
i
⋅<⋅⋅∑
−
=
1
0
.
Разделив обе части на ,M получим (2), что и требовалось доказать.
Задача восстановления большого числа U по его остаткам iu , 1,0 −= ni
имеет квадратичную сложность )( 2nO , где n -разрядность числа U . Лемма 2
показывает, что при восстановлении числа U по его остаткам может превышать
модуль ,M и что задача проверки превышения модуля M числом U имеет
линейную сложность.
Из соотношения (2) видно, что если iii mhu ,, не превышают машинное сло-
во, то необходимо n однословных операций умножения и n2 однословных
операций деления. С учетом того, что деление происходит нацело, в соотноше-
ние (2) нужно учесть выравнивающий коэффициент 2 .ω
1
0
21
,
2
i
n
i i m
i i
u h
n
m
ω−
ω
=
⋅
<
∑
где ω – количество бит в выравнивающем коэффициенте.
Операции с выравнивающим коэффициентом 2ω являются быстрыми,
так как они реализуются линейными сдвигами.
Следующая теорема показывает, что перевод числа из одной системы остат-
ков в другую можно выполнить без восстановления числа (при этом учитывает-
ся ранее доказанный критерий проверки (лемма 2)).
Теорема 2. Пусть заданы две системы в остатках с модулями ∏
−
=
=
1
0
n
i
imM ,
∏
−
=
′=′
1
0
n
i
imM такими, что 1),( =ij mm , 1),( =′′ ij mm , ji ≠ , и число MU < име-
ет следующие остатки: im
uU
i
= , 1,0 −= ni . Тогда сложность представления
числа U в системе в остатках с модулем M ′ , где MM >′ , можно выразить
следующими априорными оценками сложности без учета предвычислений:
nnnC 2)( 2* += , nnC =÷ )( , nnC 2)( = ,
где )(* nC , )(nC÷ – количество однословных операций умножения и деления,
)(nC – число операций взятия по однословному модулю.
Доказательство. Модули M и M ′ составляют n однословных модулей.
Вычислим некоторые величины, которые понадобятся далее для представления
числа U в системе остатков im′ , 1,0 −= ni .
ОПТИМИЗАЦИЯ МЕТОДА МОНТГОМЕРИ ЗА СЧЕТ ИСПОЛЬЗОВАНИЯ ОДНОСЛОВНЫХ …
Компьютерная математика. 2010, № 1 77
Матрица перехода W ′ содержит
imjij Mw
′
=′ , ii mMM = , 1,0, −= nji
и известно представление модуля M в остатках
imi Mm ′=′′ , 1,0 −= ni .
Определим вектор F следующим образом:
imiii huf = , 1=⋅
imii Mh , 1,0 −= ni . (3)
При восстановлении числа U по его остаткам, используя формулу (1),
выражение (до взятия по модулю M ) может превышать M ( MU
M
< ).
Коэффициент превышения будет следующим:
1
0
1 2
2
n
i
i i
f
k
m
ω−
ω
=
⋅=
∑ . (4)
Очевидно, что k находится в диапазоне nk <≤0 .
С учетом коэффициента превышения k n -разрядное число U в системе
остатков im′ можно представить в виде:
i
i
j
j m
n
j
ijj
m
m
m
n
j
ijji mkwfmkwfu
′
−
=
′
′
′
−
=
′′−
′=′′−′=′ ∑∑ )()(
1
0
1
0
, 1,0, −= nji . (5)
С учетом соотношений (3)–(5) находим, что число однословных умножений
равно nn 22 + , число однословных делений равно n и необходимо выполнить
n2 операций по однословному модулю, что и требовалось доказать.
Считаем, что использование выравнивающего коэффициента 2ω в формуле
(4) не увеличивает сложность, так как операции с этим коэффициентом реали-
зуются линейными сдвигами. Выбор ω зависит от количества простых множи-
телей n и, возможно, от величин самих простых множителей.
Заметим, что существуют методы, которые позволяют выполнить перевод
менее чем за nn 22 + операций однословного умножения.
Оптимизации метода Монтгомери за счет использования китайской
теоремы об остатках. Предложенный метод реализует операцию
N
VUR ⋅=
умножения двух n -разрядных чисел U и V по n -разрядному модулю N .
Использование двух систем классов связано с тем, что алгоритм 1 на шагах
2 и 3 содержит две медленные операции в обычной арифметике – умножение по
многоразрядному модулю M и деление на многоразрядное M нацело. Нахож-
дение остатка по многоразрядному модулю M происходит в той же системе
классов M . При этом остатком по сложному модулю M являются остатки
в системе классов im , которые вычисляются автоматически после каждой опе-
рации в этой системе классов. Операцию деления на M в шаге 3 можно заме-
нить операцией умножения в системе классов M ′ .
А.Н. ТЕРЕЩЕНКО
Компьютерная математика. 2010, № 1 78
Многоразрядные числа M и M ′ не являются степенью двойки.
Необходимо выполнить следующие предвычисления.
С помощью расширенного алгоритма Евклида находим числа 1−M и 1−N
такие, что 111 =⋅−⋅ −− NNMM .
Представляем N и 1−N в остатках
imi Nn = ,
imi Nn
′
−− = 11 ,
imi Nn ′=′ .
Находим числа ih , ih′ такие, что 1=⋅
imii Mh , ii mMM = , 1),( =ii mM ,
1=′⋅′ ′imii Mh , ii mMM ′′=′ , 1),( =′′ ii mM , 1,0 −= ni .
Вычисляем матрицу W ′ , где
imjij Mw
′
=′ , 1,0, −= nji , используемую для
перевода промежуточного результата из системы классов im в систему классов
im′ . Также находим
imi Mm ′=′′ , 1,0 −= ni .
Аналогично вычисляется матрица W , где
imjij Mw ′= , 1,0, −= nji ,
используемая для обратного перевода промежуточного результата из системы
классов im′ в систему классов im . Для этого также необходимо найти
imi Mm ′=′′′ , 1,0 −= ni , представляющий модуль M ′ в системе остатков im .
Операцию деления на число M в системе классов im′ заменим умножением
числа ÷M такого, что
imi Mm
′
÷÷ =′ , 1=′′⋅′
′
÷
imii mm ,
imi Mm ′=′′ , 1,0 −= ni .
Найдем N -остатки чисел U и V
N
MUU ⋅= ,
N
MVV ⋅= ;
imi Uu = ,
imi Uu
′
=′ ,
imi Vv = ,
imi Vv
′
=′ , 1,0 −= ni .
Алгоритм 2. Одновременное вычисление в двух системах остатков.
Шаг 1.
imiii vut = ,
imiii vut ′
′′=′ , 1,0 −= ni .
im
VUT ⋅=⇔ .
Шаг 2.
imiii nts 1−= , 1,0 −= ni .
im
NTS 1−⋅=⇔ .
Шаг 3. Переход в систему остатков M ′ .
Шаг 3, а.
imiii hsf = , 1,0 −= ni ;
Шаг 3, б.
1
0
1 2
2
n
i
i i
f
k
m
ω−
ω
=
⋅=
∑ ;
Шаг 3, в.
im
n
j
jiji fws
′
−
=
∑ ′=′
1
0
,
imiii mkss ′
′′−′=′ , 1,0 −= ni .
im
NTS
′
−⋅=⇔ 1 .
ОПТИМИЗАЦИЯ МЕТОДА МОНТГОМЕРИ ЗА СЧЕТ ИСПОЛЬЗОВАНИЯ ОДНОСЛОВНЫХ …
Компьютерная математика. 2010, № 1 79
Шаг 4.
imiiii sntt ′
′′+′=′ 1,0 −= ni .
im
SNTT ′⋅+=⇔ .
Шаг 5.
imiii mtt
′
÷′′=′ . ( )
im
MSNTT ′⋅+=⇔ .
Шаг 6. Возврат в исходную систему остатков M .
Шаг 6, а.
imiii htf ′
′′=′ , 1,0 −= ni ;
Шаг 6, б.
′
⋅′=′ ∑
−
=
1
0
2
2
1 n
i i
i
m
f
k
ω
ω ;
Шаг 6, в.
im
n
j
jiji fwt ∑
−
=
′=
1
0
,
imiii mktt ′′′′−= , 1,0 −= ni .
( )
im
MSNTT ⋅+=⇔ .
Алгоритм 2 можно описать так. На шаге 1 вычисления происходят в двух
системах сложных остатков M и M ′ . Шаг 2 выполняется только в классе ос-
татков M . На этом шаге находится остаток по модулю M . Далее на шаге 3 ре-
зультат переводится в систему классов M ′ , чтобы выполнить вычисление толь-
ко в системе классов M ′ на шагах 4 и 5, которые соответствуют шагу 3 алго-
ритма 1. На шаге 4 вычисляется числитель SNT ⋅+ , причем операция
imiiii sntt += отсутствует, так как в системе классов M числитель SNT ⋅+
делится нацело на M . Соответственно, 0=⋅+
im
SNT . Деление на M наце-
ло выполняется на шаге 5. Далее результат шага 5 переводится обратно в систе-
му остатков M , после чего получаем представление результата в двух системах
классов M и M ′ .
После шага 6 оба числа T и T ′ содержат R как результат умножения чи-
сел U и V в системах классов M и M ′ :
N
MVUR 1−⋅⋅= . (6)
Для восстановления результата умножения чисел U и V по модулю N не-
обходимо число R из формулы (6) умножить на 1−M по модулю N .
NN
VUMRR ⋅=⋅= −1 , (7)
53061816915813
34321
1 =⋅=⋅ −
N
MR , 5306291913100
34321
=⋅=⋅
N
VU ,
что равносильно повторному выполнению шагов начиная со 2-го по 6-ой с по-
следующим восстановлением R из it .
После шага 6 результаты в остатках классов M и M ′ могут быть использо-
ваны без дополнительных затрат для следующей итерации возведения в степень
по модулю.
А.Н. ТЕРЕЩЕНКО
Компьютерная математика. 2010, № 1 80
Теорема 3. Если числа U и V n -разрядные, то количество операций в ал-
горитме 2 можно выразить следующими априорными оценками:
nnnC 92)( 2* += , nnC 2)( =÷ , nnC 9)( = ,
где )(* nC , )(nC÷ – количество однословных операций умножения и деления,
)(nC – число операций взятия по однословному модулю.
Доказательство. В алгоритме 2 на шаге 2 происходит переход в систему
классов M ′ , а на шаге 6 переход обратно в систему остатков M . Согласно тео-
реме 2 каждый переход можно выразить следующими априорными оценками
сложности: nnnC 2)( 2* += , nnC =÷ )( , nnC 2)( = .
Шаги 1, 2, 4, 5 содержат дополнительно 5 однословных умножений по одно-
словному модулю. Таким образом, общая оценка сложности составляет
nnnC 92)( 2* += , nnC 2)( =÷ , nnC 9)( = . Что и требовалось доказать.
Для предложенного алгоритма необходимо большее число предвычислений
и подбор вначале n2 взаимно простых однословных модулей, которые состав-
ляют сложные модули M и M ′ . В конечном итоге, затраты на предвычисления
окупаются, если использовать алгоритм для возведения в степень по модулю.
Приведем пошаговый пример умножения 13100=U и 2919=V по моду-
лю 34321=N в таблице, где 36465=M , 392863=′M , MMN ′<< .
ТАБЛИЦА
1715131136465 ⋅⋅⋅==M
)17,15,13,11(),,,( 3210 =mmmm
)2145,2431,2805,3315(),,,( 3210 =MMMM
)6,1,4,3(),,,( 3210 =hhhh , 1=⋅
imii Mh
31292319392863 ⋅⋅⋅==′M
)31,29,23,19(),,,( 3210 =′′′′ mmmm
12673,13547,17081,20677(),,,( 3210 =′′′′ MMMM
)5,22,20,4(),,,( 3210 =′′′′ hhhh ,
1=′⋅′
′imii Mh
13432119304181963646511 =⋅−⋅=⋅−⋅ −− NNMM
)9,14,12,10(),,,( 1
3
1
2
1
1
1
0 =−−−− nnnn ,
imi Nn 11 −− =
)4,14,5,7(),,,( 3210 =′′′′ nnnn ,
imi Nn ′=′
11822=⋅=
N
MUU , 11914=⋅=
N
MVV
)7,2,5,8(),,,( 3210 =uuuu ,
imi Uu = ,
)14,4,6,1(),,,( 3210 =vvvv ,
imi Vv =
)11,19,0,4(),,,( 3210 =′′′ uuuu ,
imi Uu
′
=′
)10,24,0,1(),,,( 3210 =′′′′ vvvv ,
imi Vv
′
=′
=
815135
132117
111127
1698
W ,
imjij Mw ′=
=′
6131529
2824219
616223
1718129
W ,
imjij Mw
′
=′
ОПТИМИЗАЦИЯ МЕТОДА МОНТГОМЕРИ ЗА СЧЕТ ИСПОЛЬЗОВАНИЯ ОДНОСЛОВНЫХ …
Компьютерная математика. 2010, № 1 81
Окончание таблицы
)10,13,3,9(),,,( 3210 =′′′′′′′′′′′′ mmmm ,
imi Mm ′=′′′
)9,12,10,4(),,,( 3210 =′′′′′′′′ mmmm ,
imi Mm ′=′′
8315013=÷M , 1=⋅
′
÷
M
MM , )7,17,7,5(),,,( 3210 =′′′′ ÷÷÷÷ mmmm ,
imi Mm
′
÷÷ =′
Шаг 1. )13,8,4,8(),,,( 3210 =tttt ,
imiii vut ⋅= ,
)17,21,0,4(),,,( 3210 =′′′′ tttt ,
imiii vut ′
′⋅′=′
Шаг 2. )15,7,9,3(),,,( 3210 =ssss ,
imiii nts 1−⋅=
Шаг 3, а. )5,7,10,9(),,,( 3210 =ffff ,
imiii hsf ⋅=
Шаг 3, б.
⋅=
= ∑
=
3
0
12
1212
2
2
1
21204.70588+71911.46666+
+13150.76923+73351.27272
2
1
i i
i
m
f
k
4096÷96162.347656252 ===k
Шаг 3, в. )5,19,21,13(),,,( 3210 =′′′′ ssss ,
imj
jiji fws
′=
∑ ′=′
3
0
)18,24,1,5()13,5,1,5()9,12,10,4(2)5,19,21,13(),,,( 3210 =−−=−=′′′′ ssss
),,,(),,,(),,,( 321032103210 mmmmkssssssss ′′′′′′′′−′′′′=′′′′ ,
imiii mkss ′
′′−′=′
Шаг 4. )27,9,5,1(),,,( 3210 =′′′′ tttt ,
imiiii sntt ′
′′+′=′
Шаг 5. )3,8,12,5(),,,( 3210 =′′′′ tttt ,
imiii mtt
′
÷′′=′
Шаг 6, а. )15,2,10,1(),,,( 3210 =′′′′ ffff ,
imiii htf ′
′′=′
Шаг 6, б.
′
⋅′=
=′ ∑
=
3
0
12
1212
2
2
1
41981.93548+6282.482758+
+51780.86956+4215.578947
2
1
i i
i
m
f
k
4096425811.039550781 ÷===′k
Шаг 6, в. )13,1,8,4(),,,( 3210 =tttt ,
imj
jiji fwt ∑
=
′=
3
0
)3,3,5,6()3,12,5,5()10,13,3,9(1)13,1,8,4(),,,( 3210 =−−−=−=tttt
),,,(),,,(),,,( 321032103210 mmmmktttttttt ′′′′′′′′′′′′′−= ,
imiii mktt ′′′′−=
Полученные значения )3,3,5,6(),,,( 3210 =tttt представляют значение R
в остатках im . При восстановлении )3,3,5,6( дает 15813. Тот же результат мож-
но получить, воспользовавшись формулой (6)
15813181691191411822
34321
1 =⋅⋅=⋅⋅= −
N
MVUR .
А.Н. ТЕРЕЩЕНКО
Компьютерная математика. 2010, № 1 82
Хотя пример содержит 4-х словные модули M и M ′ , алгоритм 2 работает
для более длинных модулей.
Число одноословных операций умножения в методе Монтгомери (лемма 1)
и в предложенном методе (теорема 3) составляет 1
23 Cn + и 2
22 Cn + соответ-
ственно, где 1C и 2C – коэффициенты с линейной сложностью. Таким образом,
предложенный метод на каждой итерации имеет на треть меньше операций од-
нословных умножений без учета пред- и поствычислений.
Заключение. В данной работе описана оптимизация метода Монтгомери
вычисления остатка умножения двух n -разрядных чисел по n -разрядному мо-
дулю за счет одновременного вычисления в двух системах сложных остатков
M и M ′ , которые сводятся к однословным умножениям по однословному мо-
дулю. Показан переход из одной системы остатков в другую систему остатков
без промежуточного восстановления числа из остатков. Приведены пример в
виде таблицы и пошаговый алгоритм вычисления остатка умножения двух
n -разрядных чисел по n -разрядному модулю с использованием предложенного
метода. Показано, что предложенный метод на каждой итерации имеет на одну
треть меньше операций однословного умножения, чем метод Монтгомери.
А.М. Терещенко
ОПТИМІЗАЦІЯ МЕТОДУ МОНТГОМЕРІ ЗА РАХУНОК ВИКОРИСТАННЯ
ОДНОСЛІВНИХ МНОЖЕНЬ ЗА ОДНОСЛІВНИМ МОДУЛЕМ
Розглядається оптимізація множення за модулем, від часу виконання якої в основному зале-
жить швидкодія асиметричної криптографії. Пропонується оптимізація методу Монтгомері
обчислення лишку. Показано, що множення n-розрядних чисел за n-розрядним модулем мо-
жна привести до однослівних множень за однослівним модулем.
A.N. Tereshchenko
OPTIMISATION OF MULTIPRECISION MONTGOMERY'S METHOD AT THE EXPENSE OF
USING A SINGLE-PRECISION MULTIPLICATION MODULO SINGLE-PRECISION INTEGER
A modular multiplication that has a considerable influence on asymmetric cryptography
performance is considered. An optimization of Montgomery's method of modulo calculation is
proposed. It is shown that n-dimensional multiplication modulo n can yield a single precision
multiplication by single precision module.
1. Кнут Д. Искусство программирования для ЭВМ: Пер. с англ. / Под ред. Бабенко. – М:
Мир, 1977. – Т. 2. – 734 с.
2. Задірака В., Олексюк О. Комп’ютерна арифметика багаторозрядних чисел. – К., Наук.
видання, 2003. – 263 с.
3. Макклеллан Дж.Х., Рейдер Ч.М. Применение теории чисел в цифровой обработке сигна-
лов. – М.: Радио и связь, 1983. – С. 17–21.
4. Montgomery P.L. Modular Multiplication Without Trial Division // Math. Comp. – 1985. –
T. 44, N 170. – Р. 519 – 521.
Получено 18.12.2009
Îá àâòîðå:
Терещенко Андрей Николаевич,
аспирант Института кибернетики имени В.М. Глушкова НАН Украины.
teramidi@ukr.net
|
| id | nasplib_isofts_kiev_ua-123456789-84570 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | ХХХХ-0003 |
| language | Russian |
| last_indexed | 2025-12-07T18:25:18Z |
| publishDate | 2010 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Терещенко, А.Н. 2015-07-10T14:41:56Z 2015-07-10T14:41:56Z 2010 Оптимизация метода Монтгомери за счет использования однословных умножений по однословному модулю / А.Н. Терещенко // Компьютерная математика: сб. науч. тр. — 2010. — № 1. — С. 73-82. — Бібліогр.: 4 назв. — рос. ХХХХ-0003 https://nasplib.isofts.kiev.ua/handle/123456789/84570 681.511:3 Рассматривается операция умножения по модулю, от быстродействия которой в основном зависит быстродействие ассиметричной криптографии. Предлагается оптимизация метода Монтгомери нахождения остатка. Показано, что умножение n-разрядных чисел по n-разрядному модулю можно привести к однословным умножениям по однословному модулю. Розглядається оптимізація множення за модулем, від часу виконання якої в основному залежить швидкодія асиметричної криптографії. Пропонується оптимізація методу Монтгомері обчислення лишку. Показано, що множення n-розрядних чисел за n-розрядним модулем можна привести до однослівних множень за однослівним модулем. A modular multiplication that has a considerable influence on asymmetric cryptography performance is considered. An optimization of Montgomery's method of modulo calculation is proposed. It is shown that n-dimensional multiplication modulo n can yield a single precision multiplication by single precision module. ru Інститут кібернетики ім. В.М. Глушкова НАН України Компьютерная математика Оптимизация вычислений Оптимизация метода Монтгомери за счет использования однословных умножений по однословному модулю Оптимізація методу Монтгомері за рахунок використання однослівних множень за однослівним модулем Optimisation of multiprecision Montgomery's method at the expense of using a single-precision multiplication modulo single-precision integer Article published earlier |
| spellingShingle | Оптимизация метода Монтгомери за счет использования однословных умножений по однословному модулю Терещенко, А.Н. Оптимизация вычислений |
| title | Оптимизация метода Монтгомери за счет использования однословных умножений по однословному модулю |
| title_alt | Оптимізація методу Монтгомері за рахунок використання однослівних множень за однослівним модулем Optimisation of multiprecision Montgomery's method at the expense of using a single-precision multiplication modulo single-precision integer |
| title_full | Оптимизация метода Монтгомери за счет использования однословных умножений по однословному модулю |
| title_fullStr | Оптимизация метода Монтгомери за счет использования однословных умножений по однословному модулю |
| title_full_unstemmed | Оптимизация метода Монтгомери за счет использования однословных умножений по однословному модулю |
| title_short | Оптимизация метода Монтгомери за счет использования однословных умножений по однословному модулю |
| title_sort | оптимизация метода монтгомери за счет использования однословных умножений по однословному модулю |
| topic | Оптимизация вычислений |
| topic_facet | Оптимизация вычислений |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/84570 |
| work_keys_str_mv | AT tereŝenkoan optimizaciâmetodamontgomerizasčetispolʹzovaniâodnoslovnyhumnoženiipoodnoslovnomumodulû AT tereŝenkoan optimízacíâmetodumontgomerízarahunokvikoristannâodnoslívnihmnoženʹzaodnoslívnimmodulem AT tereŝenkoan optimisationofmultiprecisionmontgomerysmethodattheexpenseofusingasingleprecisionmultiplicationmodulosingleprecisioninteger |