2 ^ N мод (м) алгоритм

Question

В классе нам представили алгоритм для 2 ^ n mod (m).

    to find 2^n mod(m){  
      if n=0 {return 1;}  

      r=2^(n-1)mod(m);  
      if 2r < m {return 2r;}  
      if 2r > =m {return 2r-m;}  
    }

Нам сказали, что время выполнения равно O (n * size (m)), где size m - это количество бит в m.

Я понимаю n часть, но не могу объяснить размер (м), если это не из-за вычитания. Кто-нибудь может пролить свет на это?

Заранее спасибо.

Answer 1

Часть n понятна, как вы уже поняли. size(m) (количество цифр в m, что в основном равно log(m)) из-за мод. Даже если ваш процессор делает это за вас в одной инструкции, это займет log(m) (скажем, 32 бита) раз. Если m очень большой, как это обычно бывает с ключами шифрования, это может стать значительным.

Почему количество цифр в m? Запомни разделение:

abcdefghijk | xyz
            |-----
alm         | nrvd...
 opq
  stu
   wabc
    .......

Количество раз, когда вы делаете минус, - самое большее количество цифр в дивиденде.

Answer 2

Я считаю, что это используется в криптографии (так называемая необратимая функция ).

Если нам нужно вычислить (2**n) mod m рекурсивно, это будет наиболее очевидный способ сделать это.Поскольку глубина рекурсии равна n, сложность O(n) очевидна.

Однако, если мы хотим поддерживать произвольный размер m (в криптографии возможны 512-битные ключи, и онибольше, чем любой арифметический регистр), мы также должны учитывать, что (в большинстве случаев нам не нужно использовать арифметику произвольной точности, поэтому этот термин обычно равен 1).

EDIT @Mysticial: Функция явно не вызывает аппаратную mod операцию, все, что она делает - это сдвиг и вычитание.сдвиг всегда O(1), а сложение / вычитание O(ceil(m/sizeof_ALU_precision))