Лучшие способы реализации операции по модулю (вопрос об алгоритме)

Question

Недавно я пытался реализовать модульный экспонент. Я пишу код на 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}
}

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

Answer 1

Я не уверен, что вы там рассчитываете, если честно. Вы говорите о работе по модулю, но обычно операция по модулю находится между двумя числами a и b, и ее результатом является остаток от деления a на b. Где в вашем псевдокоде a и b ...?

В любом случае, может быть, это поможет: a mod b = a - floor(a / b) * b.

Я не знаю, быстрее это или нет, это зависит от того, можете ли вы делить и умножать быстрее, чем много вычитаний.

Еще один способ ускорить вычитание - использовать бинарный поиск. Если вы хотите a mod b, вам нужно вычесть b из a до тех пор, пока a не станет меньше b. Так что в основном вам нужно найти k такой, что:

a - k*b < b, k is min

Один из способов найти это k - это линейный поиск:

k = 0;
while ( a - k*b >= b )
    ++k;

return a - k*b;

Но вы также можете выполнить бинарный поиск (только несколько тестов, но они работали на всех):

k = 0;
left = 0, right = a
while ( left < right )
{
    m = (left + right) / 2;
    if ( a - m*b >= b )
       left = m + 1;
    else
       right = m;
}

return a - left*b;

Я предполагаю, что решение для двоичного поиска будет самым быстрым при работе с большими числами.

Если вы хотите вычислить a mod b и только a - это большое число (вы можете хранить b для примитивного типа данных), вы можете сделать это еще быстрее:

for each digit p of a do
    mod = (mod * 10 + p) % b
return mod

Это работает, потому что мы можем написать a как a_n*10^n + a_(n-1)*10^(n-1) + ... + a_1*10^0 = (((a_n * 10 + a_(n-1)) * 10 + a_(n-2)) * 10 + ...

Я думаю, что бинарный поиск - это то, что вы ищете.

Answer 2

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

Сдвиг модуля, который вы выполняете, приводит вас к полному алгоритму деления (по модулю просто берется остаток).

РЕДАКТИРОВАТЬ Вот моя реализация в Python:

def mod_mul(a,b,m):
    result = 0
    a = a % m
    b = b % m
    while (b>0):
        if (b&1)!=0:
            result += a
            if result >= m: result -= m
        a = a &lt&lt 1
        if a>=m: a-= m
        b = b>>1
    return result

Это просто модульное умножение (результат = a * b mod m). Операции по модулю сверху не нужны, но служат напоминанием о том, что алгоритм предполагает, что a и b меньше m.

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

Answer 3

Этот тест (modulus(n-1) != 1) // немного теста?

- кажется избыточным в сочетании с (modulus<result).

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

Если мы можем легко выполнять побитовые тесты, это может быть быстро:

m=msb_of(modulus)

while( result>0 ) 
{
  r=msb_of(result) //countdown from prev msb onto result
  shift=r-m        //countdown from r onto modulus or 
                   //unroll the small subtraction 

  takeoff=(modulus<<(shift))  //or integrate this into count of shift

  result=result-takeoff;  //necessary subtraction

  if(shift!=0 && result<0)
  { result=result+(takeoff>>1); }

  } //endwhile

if(result==0) { return result }
else          { return result+takeoff }

(непроверенный код может содержать ошибки)

result постепенно уменьшается на modulus, смещенное для соответствия старшим значащим битам.

После каждого вычитания: result имеет шанс ~ 50/50 потерять более 1 мсб. Он также имеет ~ 50/50 шансов стать отрицательным, добавление половины того, что было вычтено, всегда снова положит его в позитив. > его следует вернуть в положительное значение, если сдвиг не был = 0

Рабочий цикл завершается, когда result не работает, а значение 'shift' равно 0.

Answer 4

Для самого модуля я не уверен. Что касается модуля как части большей модульной экспоненциальной операции, вы искали умножение Монтгомери , как упомянуто на странице википедии по модульному возведению в степень ? Прошло много времени с тех пор, как я изучал этот тип алгоритма, но, насколько я помню, он обычно используется для быстрого модульного возведения в степень.

edit: что бы ни стоило, ваш алгоритм по модулю на первый взгляд кажется нормальным. Вы в основном делаете деление, которое является алгоритмом повторного вычитания.