Комментарии 11
Что-то все формулы в статье исходным латексом отображаются.
лестница Монтгомери выглядит странно. Обычно для защиты от side-channel требуют чтобы в коде не было if зависящих от входных данных. А в описанном виде скорость работы будет отличаться - если почти все биты 0 (или 1), то предсказатель переходов будет все время угадывать и вычисление завершится быстрее чем если биты чередуются.
Насколько я помню, нахождение самого оптимального (по числу умножений) алгоритма возведения в степень - это NP задача. Собственно, отсюда и так много способов, которые пытаются приблизиться к оптимуму для разных видов входных значений.
Из забавного. Где-то в средней школе моя мама (преподаватель физики в ВУЗе) объясняла мне возведение в степень. Я увидел, что надо перемножать числа много-много раз, ужаснулся и сказал, что-то типа - это конечно понятно - в смысле определение, а теперь, как это делать по-настоящему, т.е. по-быстрому?
Что существуют "быстрые" операции я тогда не знал, но чувствовал!
Пишут, что метод множителей широко применяется в криптографии. То есть вы предлагаете использовать факторизацию в задачах, завязаных на невозможности проведения факторизации в разумные сроки? Если я, в условном диффи-хеллмане, оперирую 4096 битными A и B, вы полагаете, что их факторизация ускорит вычисления степеней, а не замедлит на 100 лет?
Интересно а что вычисляется сложнее для больших чисел по алгоритмам
Возведение в произвольную степень или вычисление корня произвольной степени ?
У вас кажеться ошибка в коде, в первом коде:
power(val*val,(p-1)/2)
Кажеться там должно быть :
my_power(val*val,(p-1)/2)
Алгоритмы быстрого возведения в степень