Умножение Монтгомери - 32-битный регистр против 64-битного регистра

Question

Мне нужно рассчитать разницу в скорости между выполнением страницы умножения Монтгомери 602-603 с размером слова / регистром размера 32 против 64.

Пока это то, что я понимаю:

• x и y представлены массивами из нескольких слов длиной n, где n = m/w, а w - размер регистра (32 или 64).
• Общее число однозначных умножений в умножении Монтгомери составляет n*(2 + 2*n), где n представляет длину числа массивов слов.
• Я предполагаю, что умножение двух однозначных чисел занимает 1 такт на каждом из компьютеров.

Как я могу собрать все это вместе, чтобы представить количество тактов, необходимых для умножения Монтгомери на компьютере с 32-разрядным регистром или 64-разрядным регистром?

Answer 1

Количество циклов для умножения Монтгомери с множественной точностью действительно будет n(2+2*n) если бы все промежуточные операнды и результаты умножения одинарной точности были доступны в регистрах. Для криптографических операций это вряд ли возможно, так как m обычно 1024 или больше. Предполагая, что 32-битные регистры (xy R ^ -1 mod m) потребуют 192 регистра только для хранения операндов (3*(1024/32)). На самом деле вам нужно принять во внимание доступ к памяти, чтобы ответить на этот вопрос.

Переписать алгоритм с обращениями к памяти (при условии, что умножения могут выполняться параллельно с загрузкой / хранением):

1. За i от 0 до n: a_i <- 0
2. За i от 0 до (n-1) сделать следующее:
   1. получать a_0
   2. получать y_0
   3. получать x_i
   4. вычисление u_i <- (a_0 + x_i*y_0)m' mod b, хранить u_i в реестре
   5. c = 0 (Вычислительный A <- (A + x_i*y + u_i*m)/b)
   6. за j от 0 до (n-1):
      1. получать a_j
      2. получать y_j
      3. вычисление (cv) = a_j + x_i*y_j + c, Выборка m_j
      4. вычисление (cv) = (cv) + u_i*m_j, если j>0 Store a_{j-1} <- v
   7. хранить a_n <- c а также a_{n-1} <- v
3. Если A >= m затем A <- A − m,
4. Возвращение (A).

Надеюсь это поможет.