Алгоритмы быстрого возведения в степень

Что-то все формулы в статье исходным латексом отображаются.

лестница Монтгомери выглядит странно. Обычно для защиты от side-channel требуют чтобы в коде не было if зависящих от входных данных. А в описанном виде скорость работы будет отличаться - если почти все биты 0 (или 1), то предсказатель переходов будет все время угадывать и вычисление завершится быстрее чем если биты чередуются.

Насколько я помню, нахождение самого оптимального (по числу умножений) алгоритма возведения в степень - это NP задача. Собственно, отсюда и так много способов, которые пытаются приблизиться к оптимуму для разных видов входных значений.

Из забавного. Где-то в средней школе моя мама (преподаватель физики в ВУЗе) объясняла мне возведение в степень. Я увидел, что надо перемножать числа много-много раз, ужаснулся и сказал, что-то типа - это конечно понятно - в смысле определение, а теперь, как это делать по-настоящему, т.е. по-быстрому?
Что существуют "быстрые" операции я тогда не знал, но чувствовал!

Пишут, что метод множителей широко применяется в криптографии. То есть вы предлагаете использовать факторизацию в задачах, завязаных на невозможности проведения факторизации в разумные сроки? Если я, в условном диффи-хеллмане, оперирую 4096 битными A и B, вы полагаете, что их факторизация ускорит вычисления степеней, а не замедлит на 100 лет?

Интересно а что вычисляется сложнее для больших чисел по алгоритмам

Возведение в произвольную степень или вычисление корня произвольной степени ?

У вас кажеться ошибка в коде, в первом коде:

power(val*val,(p-1)/2)

Кажеться там должно быть :

my_power(val*val,(p-1)/2)