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

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

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

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

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

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

\{a+kN\colon k\in \mathbf {Z} \},

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

{\bar {a}}\equiv {\bar {b}}{\pmod {N}}.

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

Арифметика над классами остатков выполняется путем сначала выполнения целочисленных арифметических операций над их представителями. Выход целочисленной операции определяет класс остатка, а результат модульной операции определяется путем вычисления представителя класса остатка. Например, если $N = 17$ , то сумма классов вычетов $7$ и $15$ вычисляется путем нахождения целочисленной суммы $7 + 15 = 22$ , а затем определения $22 по модулю 17$ , целого числа от 0 до 16, разница которого с 22 кратна из 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,$ можно выразить, применив теорему Евклида о делении :

ab=qN+r,

где $q$ - частное $\lfloor ab/N\rfloor$ и $r$ , остаток, находится в интервале $[0, N - 1]$ . Остаток $r$ равен $ab mod N.$ Определить $r$ можно, вычислив $q$ , а затем вычитая $qN$ из $ab$ . Например, снова с $N=17$ , произведение $7 \cdot 15$ определяется путем вычисления $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 по модулю 17 = 11$ , $500 по модулю 17 = 7$ , $700 по модулю 17 = 3$ и $1500 по модулю 17 = 4$ .

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

aR+bR=(a+b)R,

aR-bR=(a-b)R.

что выполнение операции в форме Монтгомери не теряет информацию по сравнению с ее выполнением в факторкольце $Z / N Z.$ Обратите внимание , Это следствие того факта, что, поскольку $gcd(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 с $R = 100$ является произведением 3 и 4, что равно 12. Поскольку 12 не делится на 100, требуются дополнительные усилия, чтобы удалить лишние коэффициент $Р.$

Удаление дополнительного множителя $R$ можно выполнить путем умножения на целое число $R'$ такое, что $RR' \equiv 1 (mod N)$ , то есть на $R',$ класс вычетов которого является модулярным обратным к $R$ mod $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.

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

Например, чтобы умножить 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$ , алгоритм работает быстрее, чем простое модульное сокращение путем деления.

function REDC is
    input: Integers R and N with gcd(R, N) = 1,
           Integer N′ in [0, R − 1] such that NN′ ≡ −1 mod R,
           Integer T in the range [0, RN − 1].
    output: Integer S in the range [0, N − 1] such that S ≡ TR⁻¹ mod N

    m ← ((T mod R)N′) mod R
    t ← (T + mN) / R
    if t ≥ N then
        return t − N
    else
        return t
    end if
end function

Чтобы убедиться в правильности этого алгоритма, сначала заметим, что $выбрано$ именно так, что $T + mN$ делится на $R.$ m Число делится на $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$ есть $TR -1 mod 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$ . На первом этапе $m$ устанавливается равным $12 \cdot 47 mod 100 = 64$ . На втором этапе $t$ устанавливается равным $(12 + 64 \cdot 17)/100$ . Обратите внимание, что $12 + 64 \cdot 17$ равно 1100, что кратно 100, как и ожидалось. $t$ установлено равным 11, что меньше 17, поэтому окончательный результат равен 11, что согласуется с вычислениями предыдущего раздела.

В качестве другого примера рассмотрим произведение $7 \cdot 15 по модулю 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, установите $m$ равным $(28 mod 10) \cdot 7 mod 10 = 196 mod 10 = 6$ . Тогда $28 + 6 \cdot 17 = 130$ , поэтому $t = 13$ . Поскольку $30 по модулю 17 = 13$ , это форма Монтгомери $3 = 7 \cdot 15 по модулю 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 мод Н))$ . Преобразование из формы Монтгомери выполняется путем вычисления $REDC(aR mod N)$ . Модульная инверсия $aR mod N$ равна $REDC((aR mod N) -1 (Р 3 мод Н))$ . Модульное возведение в степень можно выполнить с помощью возведения в степень возведением в квадрат путем инициализации исходного продукта представлением Монтгомери 1, то есть $R mod N$ , и заменой шагов умножения и возведения в квадрат на умножения Монтгомери.

Для выполнения этих операций необходимо знать как минимум $N'$ и $R 2 мод Н.$ Когда $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 мод N)(R 2 мод Н))$ . Основная операция — вычисление REDC продукта. Когда необходим автономный REDC, его можно вычислить как REDC продукта с $1 N.$ mod Единственное место, где $прямое сокращение по модулю 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 я$ . Алгоритм начинается с целого числа многоточности $T$ и сокращает его по одному слову за раз. подходящее кратное $N$ Сначала добавляется $чтобы T$ делилось на $B.$ , кратное $N$ Затем добавляется $, чтобы T$ делилось на $B. 2$ , и так далее. В конце концов $T$ делится на $R$ , и после деления на $R$ алгоритм находится в том же месте, где находился REDC после вычисления $t$ .

function MultiPrecisionREDC is
    Input: Integer N with gcd(B, N) = 1, stored as an array of p words,
           Integer R = B^r,     --thus, r = log_B R
           Integer N′ in [0, B − 1] such that NN′ ≡ −1 (mod B),
           Integer T in the range 0 ≤ T < RN, stored as an array of r + p words.

    Output: Integer S in [0, N − 1] such that TR⁻¹ ≡ S (mod N), stored as an array of p words.

    Set T[r + p] = 0  (extra carry word)
    for 0 ≤ i < r do
        --loop1- Make T divisible by Bⁱ⁺¹

        c ← 0
        m ← T[i] ⋅ N′ mod B
        for 0 ≤ j < p do
            --loop2- Add the m ⋅ N[j] and the carry from earlier, and find the new carry

            x ← T[i + j] + m ⋅ N[j] + c
            T[i + j] ← x mod B
            c ← ⌊x / B⌋
        end for
        for p ≤ j ≤ r + p − i do
            --loop3- Continue carrying

            x ← T[i + j] + c
            T[i + j] ← x mod B
            c ← ⌊x / B⌋
        end for
    end for

    for 0 ≤ i ≤ p do
        S[i] ← T[i + r]
    end for

    if S ≥ N then
        return S − N
    else
        return S
    end if
end function

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

Приведенный выше алгоритм верен по существу по тем же причинам, что и REDC. Каждый раз в $i$ цикле $m$ выбирается $так, чтобы T [i] + mN [0]$ на $B.$ делилось Тогда $мНБ я$ добавляется $Т.$ к Поскольку эта величина равна нулю по модулю $,$ ее добавление не влияет на значение $T mod N.$ N Если $m i$ обозначает значение $m,$ вычисленное на $i$ -й итерации цикла, то алгоритм устанавливает $S$ равным $T + (\sum m i B я) Н$ . Поскольку 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.

i ← 0
m ← 6 ⋅ 7 mod 10 = 2

j T       c
- ------- -
0 0485670 2    (After first iteration of first loop)
1 0485670 2
2 0485670 2
3 0487670 0    (After first iteration of second loop)
4 0487670 0
5 0487670 0
6 0487670 0

i ← 1
m ← 4 ⋅ 7 mod 10 = 8

j T       c
- ------- -
0 0087670 6    (After first iteration of first loop)
1 0067670 8
2 0067670 8
3 0067470 1    (After first iteration of second loop)
4 0067480 0
5 0067480 0

i ← 2
m ← 6 ⋅ 7 mod 10 = 2

j T       c
- ------- -
0 0007480 2    (After first iteration of first loop)
1 0007480 2
2 0007480 2
3 0007400 1    (After first iteration of second loop)
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 .
^ Мартин Кочански, «Умножение Монтгомери». Архивировано 27 марта 2010 г. в Wayback Machine, разговорное объяснение.
^ Альфред Дж. Менезес , Пол К. ван Оршот и Скотт А. Ванстон . Справочник по прикладной криптографии . ЦРК Пресс, 1996. ISBN 0-8493-8523-7 , глава 14.
^ Jump up to: ^а ^б ^с Лю, Чжэ; Гросшедль, Иоганн; Кижватов, Илья (29 ноября 2010 г.). Эффективная и устойчивая к побочным каналам реализация RSA для 8-битных микроконтроллеров AVR (PDF) . 1-й международный семинар по безопасности Интернета вещей . Токио. ( Слайды презентации .)
^ Четин К. Коч; Толга Ачар; Бертон С. Калиски-младший (июнь 1996 г.). «Анализ и сравнение алгоритмов умножения Монтгомери» (PDF) . IEEE микро . 16 (3): 26–33. CiteSeerX 10.1.1.26.3120 . дои : 10.1109/40.502403 .
^ Марк Джой и Сун-Минг Йен. «Лестница электропитания Монтгомери» . 2002.

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

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

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

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

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

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

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

[6] Марк Джой и Сун-Минг Йен. «Лестница электропитания Монтгомери» . 2002.

[1]

[2]

[3]

[4]

[5]

[6]