Модульное умножение Монтгомери

В модульных арифметических вычислениях модульное умножение Монтгомери , чаще называемое умножением Монтгомери , является методом выполнения быстрого модульного умножения. Он был введен в 1985 году американским математиком Питером Л. Монтгомери . ^[1]^[2]

Модульное умножение Монтгомери основано на специальном представлении чисел, называемом формой Монтгомери. Алгоритм использует форму Монтгомери и $б$ эффективно вычислить Montgomery формы $аб$ $мод$ $N$ . Эффективность достигается за счет избежания дорогостоящих операций по разделению. Классическое модульное умножение уменьшает произведение $ab$ двойной ширины, используя деление на $N$ и оставляя только остаток. Это деление требует оценки и исправления частных цифр. Форма Монтгомери, напротив, зависит от константы $R> N,$ которая взаимно проста с $N$ , и единственное деление, необходимое при умножении Монтгомери, - это деление на $R.$ . Константу $R$ можно выбрать так, чтобы деление на $R было$ простым, что значительно повысило скорость работы алгоритма. На практике $R$ всегда является степенью двойки, поскольку деление на степени двойки может быть реализовано с помощью битового сдвига.

Необходимость преобразовать $a$ и $b$ в форму Монтгомери и их произведение из формы Монтгомери означает, что вычисление одного произведения с помощью умножения Монтгомери происходит медленнее, чем традиционный алгоритм редукции или алгоритм редукции Барретта . Однако при выполнении множества умножений подряд, как при модульном возведении в степень , промежуточные результаты можно оставить в форме Монтгомери. Тогда начальные и конечные преобразования становятся незначительной частью общих вычислений. Многие важные криптосистемы, такие как RSA и обмен ключами Диффи – Хеллмана , основаны на арифметических операциях по модулю большого нечетного числа, и для этих криптосистем вычисления с использованием умножения Монтгомери на $R$ степень двойки быстрее, чем доступные альтернативы. ^[3]

Модульная арифметика

Пусть $N$ обозначает положительный целочисленный модуль. Фактор - кольцо $Z / N Z$ состоит из классов вычетов по модулю $N$ , то есть, ее элементы множества вида

{\ Displaystyle \ {а + кН \ двоеточие к \ в \ mathbf {Z} \},}

где $a$ варьируется от целых чисел. Каждый класс остатка представляет собой набор целых чисел, таких, что разность любых двух целых чисел в наборе делится на $N$ (и класс остатка является максимальным по отношению к этому свойству; целые числа не исключаются из класса остатка, если они не нарушают условие делимости). Класс вычетов, соответствующий $a$ , обозначается $a$ . Равенство классов вычетов называется конгруэнцией и обозначается

{\ displaystyle {\ bar {a}} \ Equiv {\ bar {b}} {\ pmod {N}}.}

Хранение всего класса остатка на компьютере невозможно, потому что класс остатка имеет бесконечно много элементов. Вместо этого классы остатков хранятся как представители. Условно эти представители представляют собой целые числа $a,$ для которых $0 \leq a \leq N - 1$ . Если является целым числом, то представитель написано $мод$ $Н$ . При написании сравнений принято отождествлять целое число с классом остатка, который оно представляет. С этой конвенции, указанное равенство записано $в$ $\equiv$ $б$ $мод$ $N$ .

Арифметика над классами остатков выполняется сначала целочисленными арифметическими действиями над их представителями. Результат целочисленной операции определяет класс остатка, а результат модульной операции определяется вычислением представителя класса остатка. Например, если $N = 17$ , то сумма классов остатков $7$ и $15$ вычисляется путем нахождения целочисленной суммы $7 + 15 = 22$ , а затем определения $22 по модулю 17$ , целого числа от 0 до 16, разность которого с 22 является кратной of 17. В данном случае это целое число 5, поэтому $7 + 15 \equiv 5 mod 17$ .

Форма Монтгомери

Если $a$ и $b$ являются целыми числами в диапазоне $[0, N - 1]$ , то их сумма находится в диапазоне $[0, 2 N - 2],$ а их разность находится в диапазоне $[- N + 1, N - 1]$ , поэтому определение представителя в $[0, N - 1]$ требует не более одного вычитания или добавления (соответственно) $N$ . Однако произведение $ab$ находится в диапазоне $[0, N 2 - 2 N + 1]$ . Сохранение промежуточного целочисленного произведения $ab$ требует вдвое больше битов, чем $a$ или $b$ , а эффективное определение представителя в $[0, N - 1]$ требует деления. Математически целое число от 0 до $N - 1$ , которое конгруэнтно $ab,$ может быть выражено с помощью теоремы Евклида о делении :

{\ displaystyle ab = qN + r,}

где $q$ - частное, а $r$ - остаток, находится в интервале $[0,$ $N$ $- 1]$ . Остальной $г$ является $абы$ $мод$ $Н$ . Определить $r$ можно, вычислив $q$ , а затем вычтя $qN$ из $ab$ . Так , например, продукт $7$ $\cdot$ $15$ определяется путем вычисления , деления и вычитания . ${\ displaystyle \ lfloor ab / N \ rfloor}$ $7\cdot 15=105$ $\lfloor 105/17\rfloor =6$ $105-6\cdot 17=105-102=3$

Поскольку вычисление $q$ требует деления, это нежелательно дорого для большинства компьютерного оборудования. Форма Монтгомери - это другой способ выражения элементов кольца, в котором модульные продукты могут быть вычислены без дорогостоящих делений. В то время как подразделения по - прежнему необходимы, они могут быть сделаны в отношении другого делителя $R$ . Этот делитель может быть равен степени двойки, для которой деление может быть заменено сдвигом, или целым числом машинных слов, для которых деление может быть заменено пропуском слов. Эти подразделения работают быстро, поэтому большая часть затрат на вычисление модульных продуктов с использованием формы Монтгомери - это затраты на вычисление обычных продуктов.

Вспомогательный модуль $R$ должен быть натуральным числом таким, что $gcd (R, N) = 1$ . Для вычислительных целей, необходимо также , что деление и уменьшение по модулю $R$ быть недорогими, а модуль не является полезным для модульного умножения исключением случаев , когда $R > N$ . Форма Монтгомери класса вычетов $a по$ отношению к $R$ - это $aR mod N$ , то есть она является представителем класса вычетов $aR$ . Например, предположим, что $N = 17$ и $R = 100.$ . Формы Монтгомери 3, 5, 7 и 15: $300 mod 17 = 11$ , $500 mod 17 = 7$ , $700 mod 17 = 3$ и $1500 mod 17 = 4$ .

Сложение и вычитание в форме Монтгомери аналогичны обычному модульному сложению и вычитанию из-за закона распределения:

aR+bR=(a+b)R,

aR-bR=(a-b)R.

Это является следствием того факта , что, поскольку $НОД (R, N) = 1$ , умножение на $R$ является изоморфизмом на аддитивной группе $Z / N Z$ . Например, $(7 + 15) mod 17 = 5$ , что в форме Монтгомери становится $(3 + 4) mod 17 = 7$ .

Однако умножение в форме Монтгомери кажется более сложным. Обычное произведение $aR$ и $bR$ не представляет собой произведение $a$ и $b,$ потому что оно имеет дополнительный множитель $R$ :

(aR{\bmod {N}})(bR{\bmod {N}}){\bmod {N}}=(abR)R{\bmod {N}}.

Вычислительный продукты в Монтгомери форме требует удаления дополнительного фактора $R$ . Хотя деление на $R$ $обходится$ дешево, промежуточный продукт $(aR mod N) (bR mod N)$ не делится на $R,$ потому что операция по модулю разрушила это свойство. Так, например, продукт из форм Монтгомери 7 и 15 по модулю 17 является продуктом 3 и 4, который является 12. Так как 12 не делится на 100, дополнительное усилие, чтобы удалить дополнительный фактор $R$ .

Удаление дополнительный фактор $R$ может быть сделано путем умножения на целое $R'$ такие , что $RR' \equiv 1 ( по модулю N)$ , то есть, с помощью $R'$ , чей класс вычетов является модульным обратным из $R$ по модулю $N$ . Затем, работая по модулю $N$ ,

(aR{\bmod {N}})(bR{\bmod {N}})R'\equiv (aR)(bR)R^{-1}\equiv (ab)R{\pmod {N}}.

Целое число $R'$ существует из-за предположения, что $R$ и $N$ взаимно просты. Его можно построить с помощью расширенного алгоритма Евклида . Расширенный алгоритм Евклида эффективно определяет целые числа $R'$ и $N',$ которые удовлетворяют тождеству Безу : $0 < R'< N$ , $0 < N' < R$ , и:

RR'-NN'=1.

Это показывает, что можно производить умножение в форме Монтгомери. Несложный алгоритм для умножения чисел в форме Монтгомери поэтому умножить $А.Р. моды N$ , $уш мод N$ , и $R'$ в виде целых чисел и уменьшить по модулю $N$ .

Например, чтобы умножить 7 и 15 по модулю 17 в форме Монтгомери, снова с $R = 100$ , вычислите произведение 3 и 4, чтобы получить 12, как указано выше. Расширенный алгоритм Евклида подразумевает, что $8\cdot100 - 47\cdot17 = 1$ , поэтому $R' = 8$ . Умножьте 12 на 8, чтобы получить 96, и уменьшите по модулю 17, чтобы получить 11. Это форма Монтгомери 3, как и ожидалось.

Алгоритм REDC

Хотя выше алгоритм является правильным, это медленнее , чем умножение в стандартном представлении из - за необходимости умножить на $R'$ и деления на $N$ . Редукция Монтгомери , также известная как REDC, представляет собой алгоритм, который одновременно вычисляет произведение на $R'$ и сокращает по модулю $N$ быстрее, чем наивный метод. В отличие от обычного модульного сокращения, которая сосредоточена на создании число меньше , чем $N$ , сокращение Монтгомери фокусируется на обеспечении число больше , делится на $R$ . Он делает это путем добавления небольшого числа, кратного $N,$ которое выбирается для сокращения остатка по модулю $R$ . Разделив результат на $R, вы$ получите гораздо меньшее число. Это число настолько меньше, что оно почти равно уменьшению по модулю $N$ , а вычисление редукции по модулю $N$ требует только заключительного условного вычитания. Поскольку все вычисления выполняются с использованием только сокращения и деления относительно $R$ , а не $N$ , алгоритм работает быстрее, чем прямое модульное сокращение путем деления.

Функция REDC является  ввод: Целые R и N с НОД ( R , N ) = 1 , Целое число N ′ в [0, R - 1] такое, что NN ′ ≡ −1 mod R , Целое число T в диапазоне [0, RN - 1] . вывод: целое число S в диапазоне [0, N - 1] такое, что S ≡ TR ⁻¹ mod N m ← (( T mod R ) N ′) mod R  t ← ( T + mN ) / R,  если  t ≥ N,  то  вернуть  t - N,  иначе  вернуть  t  end, если end функция

Для того, чтобы видеть , что этот алгоритм является правильным, прежде всего, что $м$ выбран именно так , что $Т + мН$ делится на $R$ . Число делится на $R$ тогда и только тогда, когда оно конгруэнтно нулю по модулю $R$ , и мы имеем:

T+mN\equiv T+(((T{\bmod {R}})N'){\bmod {R}})N\equiv T+TN'N\equiv T-T\equiv 0{\pmod {R}}.

Следовательно, $t$ - целое число. Во-вторых, на выходе получается либо $t,$ либо $t - N$ , оба из которых конгруэнтны $t mod N$ , поэтому, чтобы доказать, что выход конгруэнтен $TR -1 mod N$ , достаточно доказать, что $t$ совпадает. По модулю $N$ , $t$ удовлетворяет:

t\equiv (T+mN)R^{-1}\equiv TR^{-1}+(mR^{-1})N\equiv TR^{-1}{\pmod {N}}.

Следовательно, результат имеет правильный класс остатка. В-третьих, $m$ находится в $[0, R - 1]$ , и поэтому $T + mN$ находится между 0 и $(RN - 1) + (R - 1) N <2 RN$ . Следовательно, $t$ меньше $2 N$ , и поскольку это целое число, это помещает $t$ в диапазон $[0, 2 N - 1]$ . Следовательно, приведение $t$ к желаемому диапазону требует не более одного вычитания, поэтому результат алгоритма находится в правильном диапазоне.

Чтобы использовать REDC для вычисления произведения 7 и 15 по модулю 17, сначала преобразуйте в форму Монтгомери и умножьте на целые числа, чтобы получить 12, как указано выше. Затем примените REDC с $R = 100$ , $N = 17$ , $N' = 47$ и $T = 12$ . Первым шагом устанавливает $м$ до $12 \cdot 47 мод 100 = 64$ . Второй шаг множества $т$ к $(12 + 64 \cdot 17) / 100$ . Обратите внимание, что $12 + 64 \cdot 17$ равно 1100, что, как и ожидалось, кратно 100. $t$ установлено на 11, что меньше 17, поэтому окончательный результат равен 11, что согласуется с вычислением в предыдущем разделе.

В качестве другого примера рассмотрим произведение $7 \cdot 15 mod 17,$ но с $R = 10$ . Используя расширенный алгоритм Евклида, вычислите $-5 \cdot 10 + 3 \cdot 17 = 1$ , так что $N'$ будет $-3 mod 10 = 7$ . Формы Монтгомери 7 и 15 равны $70 по модулю 17 = 2$ и $150 по модулю 17 = 14$ соответственно. Их произведение 28 является входом $T$ в REDC, и, поскольку $28 < RN = 170$ , предположения REDC выполнены. Для запуска REDC, набор $т$ к $(28 мод 10) \cdot 7 мод 10 = 196 мод 10 = 6$ . Тогда $28 + 6 \cdot 17 = 130$ , поэтому $t = 13$ . Поскольку $30 mod 17 = 13$ , это форма Монтгомери $3 = 7 15 mod 17$ .

Арифметика в форме Монтгомери

Многие интересующие операции по модулю $N$ могут быть одинаково хорошо выражены в форме Монтгомери. Сложение, вычитание, отрицание, сравнение на равенство, умножение на целое число не в форме Монтгомери и наибольшие общие делители с $N -$ все это может быть выполнено с помощью стандартных алгоритмов. Символ Якоби можно вычислить, пока он хранится. ${\big (}{\tfrac {a}{N}}{\big )}={\big (}{\tfrac {aR}{N}}{\big )}/{\big (}{\tfrac {R}{N}}{\big )}$ ${\big (}{\tfrac {R}{N}}{\big )}$

Когда $R > N$ , большинство других арифметических операций могут быть выражены в терминах REDC. Это предположение подразумевает, что произведение двух представителей по модулю $N$ меньше $RN$ , точная гипотеза, необходимая для REDC, чтобы генерировать правильный результат. В частности, произведение $aR mod N$ и $bR mod N$ равно $REDC ((aR mod N) (bR mod N))$ . Комбинированная операция умножения и REDC часто называется умножением Монтгомери .

Преобразование в форму Монтгомери выполняется путем вычисления $REDC ((a mod N) (R 2 mod N))$ . Преобразование из формы Монтгомери выполняется вычислением $REDC (aR mod N)$ . Модульная инверсия $aR mod N$ - это $REDC ((aR mod N) -1 (R 3 mod N))$ . Модульное возведение в степень может быть выполнено с помощью возведения в степень возведения в квадрат , инициализируя начальный продукт представлением Монтгомери 1, то есть $R mod N$ , и путем замены шагов умножения и квадрата на умножение Монтгомери.

Выполнение этих операций необходимо знать по крайней мере , $N'$ и $R 2 по модулю N$ . Когда $R$ является степенью малого положительного целого числа $b$ , $N'$ может быть вычислено с помощью леммы Гензеля : обратное к $N$ по модулю $b$ вычисляется с помощью наивного алгоритма (например, если $b = 2,$ то обратное значение равно 1), и лемма используется неоднократно, чтобы найти обратный по модулю все более высокие степени $b$ , останавливаясь, когда известен обратный по модулю $R$ ; $N'$ отрицание этого обратного. Константы $R mod N$ и $R 3 mod N$ могут быть сгенерированы как $REDC (R 2 mod N)$ и как $REDC ((R 2 mod N) (R 2 mod N))$ . Основная операция - вычислить REDC продукта. Когда автономный REDC необходимо, она может быть вычислена как REDC продукта с $1 по модулю N$ . Единственное место , где прямое восстановление по модулю $N$ необходимо находится в предвычислениях $R 2 мод Н$ .

Арифметика Монтгомери на целых числах с высокой точностью

Для большинства криптографических приложений требуются числа длиной в сотни или даже тысячи бит. Такие числа слишком велики, чтобы их можно было хранить в одном машинном слове. Как правило, оборудование выполняет умножение по модулю базы $B$ , поэтому выполнение больших умножений требует объединения нескольких малых умножений. База $B$ обычно равна 2 для микроэлектронных приложений, 2 ⁸ для 8-битных прошивок ^[4] или 2 ³² или 2 ⁶⁴ для программных приложений.

Алгоритм REDC требует продуктов по модулю $R$ , и обычно $R > N,$ чтобы REDC можно было использовать для вычисления продуктов. Однако, когда $R$ является степенью $B$ , существует вариант REDC, который требует произведения только целых чисел размером с машинное слово. Предположим, что положительные целые числа с разной точностью хранятся с прямым порядком байтов , то есть $x$ хранится как массив $x [0], ..., x [ℓ - 1],$ такой, что $0 \leq x [i] < B$ для всех $i$ и $х = \sum х [я] B i$ . Алгоритм начинается с целого числа $T$ с высокой точностью и сокращает его на одно слово за раз. Во- первых соответствующее кратное $N$ добавляют , чтобы сделать $T$ делится на $B$ . Затем добавляется число, кратное $N,$ чтобы $T$ делилось на $B 2$ , и так далее. В конце концов, $T$ делится на $R$ , и после деления на $R$ алгоритм находится в том же месте, что и REDC после вычисления $t$ .

функция MultiPrecisionREDC - это  вход: целое число N с gcd ( B , N ) = 1 , сохраненное как массив из p слов, Целое число R = B ^r , - таким образом, r = log _B  R Целое число N ′ в [0, B - 1] такое, что NN ′ ≡ −1 (mod B ) , Целое число T в диапазоне 0 ≤ T < RN , хранящееся как массив из r + p слов. Выход: целое число S в [0, N - 1] такое, что TR ⁻¹ ≡ S (mod N ) , хранится как массив из p слов. Установите T [ r + p ] = 0  (дополнительное слово переноса)  для  0 ≤ i < r  do  --loop1- Сделайте T делимым на B ^{i + 1} c ← 0 m ← T [ i ] ⋅ N ′ mod B  для  0 ≤ j < p  do  --loop2- Добавить младшее слово m ⋅ N [j] и перенос из предыдущего, и найти новый перенос x ← T [ i + j ] + m ⋅ N [ j ] + c  T [ i + j ] ← x mod B  c ← ⌊ x / B ⌋  end for  для  p ≤ j ≤ r + p - i  do  --loop3 - Продолжайте носить x ← T [ i + j ] + c  T [ i + j ] ← x mod B  c ← ⌊ x / B ⌋  конец за  концом для для  0 ≤ i < p  do  S [ i ] ← T [ i + r ] end для если  S ≥ N,  тогда  верните  S - N,  иначе  верните  S  end if end function

Окончательное сравнение и вычитание производится по стандартным алгоритмам.

Вышеупомянутый алгоритм верен по существу по тем же причинам, что и REDC. Каждый раз , когда через $я$ петлю, $м$ выбрано так , что $Т [я] + мН [0]$ делится на $B$ . Затем к $T$ добавляется $mNB i$ . Поскольку эта величина равна нулю по модулю $N$ , добавляя его не влияет на величину $T$ $по модулю$ $N$ . Если $т$ $я$ обозначает значение $м$ , вычисленное в $я$ - е итерации цикла, то множество алгоритмов $S$ в $T$ $+ (E$ $м я Б I) N$ . Поскольку MultiPrecisionREDC и REDC производят одинаковый результат, эта сумма совпадает с выбором $m,$ который сделает алгоритм REDC.

Последнее слово $T$ , $T [r + p]$ (и, следовательно, $S [p]$ ), используется только для хранения переноса, так как исходный результат сокращения связан с результатом в диапазоне $0 \leq S < 2N$ . Отсюда следует, что этого лишнего слова переноса можно полностью избежать, если заранее известно, что $R \geq 2N$ . В типичной двоичной реализации это эквивалентно заявлению о том, что этого слова переноса можно избежать, если количество битов $N$ меньше, чем количество битов $R$ . В противном случае перенос будет либо нулем, либо единицей. В зависимости от процессора, это слово может быть возможно сохранить как флаг переноса вместо полноразмерного слова.

Можно объединить умножение с высокой точностью и REDC в один алгоритм. Этот комбинированный алгоритм обычно называется умножением Монтгомери. Коч, Акар и Калиски описывают несколько различных реализаций. ^[5] Алгоритм может использовать всего $p + 2$ слова памяти (плюс бит переноса).

Например, пусть $B = 10$ , $N = 997$ и $R = 1000$ . Предположим, что $a = 314$ и $b = 271$ . Монтгомери представляет $a$ и $b$ : $314000 mod 997 = 942$ и $271000 mod 997 = 813$ . Вычислите $942 \cdot 813 = 765846$ . Первоначальный вход $T$ для MultiPrecisionREDC будет [6, 4, 8, 5, 6, 7]. Число $N$ будет представлено как [7, 9, 9]. Расширенный алгоритм Евклида утверждает, что $-299 \cdot 10 + 3 \cdot 997 = 1$ , поэтому $N'$ будет 7.

я ← 0
м ← 6 ⋅ 7 мод 10 = 2j T c
- ------- -
0 0485670 2 (после первой итерации первого цикла)1 0485670 2
2 0485670 2
3 0487670 0 (после первой итерации второго цикла)4 0487670 0
5 0487670 0
6 0487670 0
я ← 1
м ← 4 ⋅ 7 мод 10 = 8j T c
- ------- -
0 0087670 6 (После первой итерации первого цикла)1 0067670 8
2 0067670 8
3 0067470 1 (после первой итерации второго цикла)4 0067480 0
5 0067480 0
я ← 2
м ← 6 ⋅ 7 мод 10 = 2j T c
- ------- -
0 0007480 2 (после первой итерации первого цикла)1 0007480 2
2 0007480 2
3 0007400 1 (после первой итерации второго цикла)4 0007401 0

Следовательно, перед окончательным сравнением и вычитанием $S = 1047$ . Последнее вычитание дает число 50. Поскольку представление Монтгомери для $314 \cdot 271 по модулю 997 = 349$ составляет $349000 по модулю 997 = 50$ , это ожидаемый результат.

При работе с основанием 2 определение правильного $m$ на каждом этапе особенно просто: если текущий рабочий бит четный, то $m$ равен нулю, а если он нечетный, то $m$ равен единице. Более того, поскольку каждый шаг MultiPrecisionREDC требует знания только младшего бита, умножение Монтгомери можно легко комбинировать с сумматором с сохранением переноса .

Атаки по побочным каналам

Поскольку редукция по Монтгомери позволяет избежать шагов коррекции, требуемых при обычном делении, когда оценки частных цифр неточны, в нем в основном отсутствуют условные переходы, которые являются основными целями атак по синхронизирующим и мощным побочным каналам ; последовательность выполняемых инструкций не зависит от значений входных операндов. Единственное исключение - это окончательное условное вычитание модуля, но его легко изменить (чтобы всегда что-то вычитать, либо модуль, либо ноль), чтобы сделать его устойчивым. ^[4] Конечно, необходимо убедиться, что алгоритм возведения в степень, построенный на основе примитива умножения, также устойчив. ^[4]^[6]

Смотрите также

Редукция Барретта

использованная литература

↑ Монтгомери, Питер (апрель 1985 г.). «Модульное умножение без пробного деления» (PDF) . Математика вычислений . 44 (170): 519–521. DOI : 10.1090 / S0025-5718-1985-0777282-X .
^ Мартин Kochanski, «Монтгомери Умножение» архивации 2010-03-27 в Wayback Machine разговорное объяснение.
↑ Альфред Дж. Менезес , Пол К. ван Оршот и Скотт А. Ванстон . Справочник по прикладной криптографии . CRC Press, 1996. ISBN 0-8493-8523-7 , глава 14.
^ a b c Лю, Чжэ; Гросшедль, Иоганн; Кижватов Илья (29 ноября 2010 г.). Эффективная и устойчивая к побочным каналам реализация RSA для 8-битных микроконтроллеров AVR (PDF) . 1-й международный семинар по безопасности Интернета вещей . Токио. ( Слайды презентации .)
^ Четин К. Коч; Толга Ачар; Бертон С. Калиски-младший (июнь 1996 г.). «Анализ и сравнение алгоритмов умножения Монтгомери» (PDF) . IEEE Micro . 16 (3): 26–33. CiteSeerX 10.1.1.26.3120 . DOI : 10.1109 / 40.502403 .
^ Марк Joye и Сунг-Мин йены. "Силовая лестница Монтгомери" . 2002 г.

внешние ссылки

Генри С. Уоррен-младший (июль 2012 г.). «Теория и практика умножения Монтгомери» (PDF) .

[montg1985-1] Монтгомери, Питер (апрель 1985 г.). «Модульное умножение без пробного деления» (PDF) . Математика вычислений . 44 (170): 519–521. DOI : 10.1090 / S0025-5718-1985-0777282-X .

[kochanski-2] Мартин Kochanski, «Монтгомери Умножение» архивации 2010-03-27 в Wayback Machine разговорное объяснение.

[3] Альфред Дж. Менезес , Пол К. ван Оршот и Скотт А. Ванстон . Справочник по прикладной криптографии . CRC Press, 1996. ISBN 0-8493-8523-7 , глава 14.

[kizhvatov-4] Лю, Чжэ; Гросшедль, Иоганн; Кижватов Илья (29 ноября 2010 г.). Эффективная и устойчивая к побочным каналам реализация RSA для 8-битных микроконтроллеров AVR (PDF) . 1-й международный семинар по безопасности Интернета вещей . Токио. ( Слайды презентации .)

[5] Четин К. Коч; Толга Ачар; Бертон С. Калиски-младший (июнь 1996 г.). «Анализ и сравнение алгоритмов умножения Монтгомери» (PDF) . IEEE Micro . 16 (3): 26–33. CiteSeerX 10.1.1.26.3120 . DOI : 10.1109 / 40.502403 .

[6] Марк Joye и Сунг-Мин йены. "Силовая лестница Монтгомери" . 2002 г.

[1]