Возведение в степень в квадрате

---

В математике и компьютерном программировании возведение в степень путем возведения в квадрат является общим методом быстрого вычисления больших положительных целых степеней числа или, в более общем смысле, элемента полугруппы , такого как многочлен или квадратная матрица . Некоторые варианты обычно называют алгоритмами возведения в квадрат и умножения или двоичным возведением в степень . Они могут иметь весьма общее применение, например, в модульной арифметике или возведении матриц в степень. Для полугрупп, для которых обычно используются аддитивные обозначения , такие как эллиптические кривыеиспользуемый в криптографии , этот метод также упоминается как удвоение и добавление .

В этом примере показано, как выполнять вычисления с помощью этого метода. Показатель степени 13 равен 1101 в двоичном формате. Биты используются в порядке слева направо. Экспонента имеет 4 бита, поэтому есть 4 итерации.${\ Displaystyle х ^ {13}}$

Сначала инициализируйте результат равным 1: .${\ Displaystyle г \ стрелка влево 1 \, (= х ^ {0})}$

Если мы напишем в двоичном виде как , то это эквивалентно определению последовательности , пуская и затем определяя для , где будет равно .${\ Displaystyle п}$${\ displaystyle b_ {k} \ cdots b_ {0}}$${\ displaystyle r_ {k + 1}, \ ldots, r_ {0}}$${\ displaystyle r_ {k + 1} = 1}$${\ displaystyle r_ {i} = r_ {i + 1} ^ {2} x ^ {b_ {i}}}$${\ Displaystyle я = к, \ ldots, 0}$${\ displaystyle r_ {0}}$${\ Displaystyle х ^ {п}}$

Хотя этот алгоритм и не является хвостовой рекурсией , его можно переписать в хвостовую рекурсию, введя вспомогательную функцию:

---