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

Проблема, которую я имею, заключается в реализации операции модуля в множителе. Я знаю, что выполнение повторных вычитаний будет работать, но это также будет медленно. Я узнал, что мог бы сдвинуть модуль, чтобы эффективно вычесть большие кратные модуля, но я думаю, что все еще могут быть лучшие способы сделать это. Алгоритм, который я использую, работает примерно так (странный псевдокод следует):

result,modulus : integer (n bits) (previously defined)
shiftcount : integer (initialized to zero)
while( (modulus<result) and  (modulus(n-1) != 1) ){
     modulus = modulus << 1
     shiftcount++
}
for(i=shiftcount;i>=0;i--){
     if(modulus<result){result = result-modulus}
     if(i!=0){modulus = modulus >> 1}
}

Итак ... это хороший алгоритм или, по крайней мере, хорошее место для начала? В Википедии на самом деле не обсуждаются алгоритмы для реализации операции по модулю, и всякий раз, когда я пытаюсь искать в другом месте, я нахожу действительно интересные, но невероятно сложные (и часто не связанные) исследовательские работы и публикации. Если есть очевидный способ реализовать это, которого я не вижу, я был бы очень признателен за некоторые отзывы.