Я заранее прошу прощения за то, что может быть плохим вопросом, поскольку я почти ничего не знаю о вычислительной сложности (или компьютерной науке в целом).
Установлено (https://en.m.wikipedia.org/wiki/Schönhage–Strassen_algorithm)), что с помощью алгоритма произведение двух n-значных чисел может быть вычислено в сложности O (n • log (n) • log (log (n))). У меня есть также слышал, что сложность операции по модулю обычно немного больше, чем умножение.
Однако, исходя из математического фона, я обнаружил, что почти во всех работах по тестированию на простоту утверждается, что МОДУЛЬНОЕ умножение с использованием Шёнхаге-Штрассена все еще имеет сложность O (n • log (n) • log (log (n))) (или, по крайней мере, это делает модульное возведение в степень).
Верно ли это (алгоритм каким-то образом включает шаг по модулю, что делает его более сложным), или многочисленные статьи ошибочны (и почему)?
Спасибо. :)