Умножение «в столбик»

Операция умножения является одной из наиболее трудоемких и вместе с функцией деления определяет время работы алгоритма.

Пусть неотрицательные целые числа а и b заданы в системе счисления с основанием B.

где 0 ≤ a_i  < B, 0 ≤ b_i < B

Самый очевидный способ умножения — умножение «в столбик».

Алгоритм 2. Умножение целых чисел «в столбик», [Молдовян Н.А. и др., 2004].

Вход. Целые числа ,  где 0 < b ≤ a.

Выход. Произведение

1.         Для i = 0, 1, ...,п- 1 положить c_i= 0

2.         Для i = 0, 1, ...,п- 1 выполнить следующие действия.

2.1. Для j = 0, 1, ...,п- 1:

2.1.1. Положить s= 0.

2.1.2. Вычислить t = c_i+j+a_ib_j+s, c_i+j=t (mod B), .

2.2. Положить c_i+n =s.

3.    Результат:

Во внешнем цикле этого алгоритма вычисляются частичные произведения , а во внутреннем — произведения , где j = 0, 1, ..., п- 1. Текущий разряд произведения равен t (mod В), а очередной перенос: . При этом на шаге 2.1.2 выполняется неравенство:

Сложность умножения в «столбик» О(n²).

Функция умножения реализована как умножение с вычислением модуля.

Код функции mult_mod (умножение по модулю) c=a*b (mod mod):

 

void mult_mod(unsigned char a[33],unsigned char b[33],unsigned char c[33]){

int i,j,k,s,t;

unsigned char d[65]={0};

for (k=0;k<=31;k++) c[k]=0; //очищение переменной

for(i=0;i<=31;i++){

s=0;

       for(j=0;j<=31;j++){

                  t=d[i+j]+a[i]*b[j]+s;

                  d[i+j]=t;

                  s=t>>8;

       }

       d[i+32]=s;

}

modul(d,mod,c); //вычисление модуля mod - глобальная переменная

}

Возведение целого числа в квадрат.

Отдельно реализована функция возведения в квадрат.

Алгоритм 3. Возведение в квадрат, [Молдовян Н.А. и др., 2004].

Вход. Целое положительное число .

Выход. Значение

1.    Для i = 0, 1, ...,п- 1 положить с_i= 0.

2.    Для i = 0, 1, ...,п- 1 выполнить следующие действия.

2.1. Положить  , , .

2.2. Для j = 0, 1, ...,п- 1 вычислить t = c_i+j+a_ia_j+s, c_i+j=t (mod B), .

2.3. Положить c_i+n =s.

Результат: с .

На шаге 2.2 алгоритма выполняется неравенство:

Это означает что t может занимать более двух разрядов в системе исчисления B.

Сложность алгоритма возведение в квадрат О().

Код функции step2 (возведение в квадрат) b=a^2 (mod mod):

 

void step2(unsigned char a[33],unsigned char b[33]){

       unsigned char c[65]={0};

       int t,s,i,j;

       for(i=0;i<=32;i++){

                  t=c[2*i]+a[i]*a[i];

                  c[2*i]=t%256;

                  s=t>>8;

                  for(j=i+1;j<=32;j++){

                              t=c[i+j]+2*a[i]*a[j]+s;

                              c[i+j]=t%256;

                              s=t>>8;

                  }

                  c[i+33]=s;

       }

       modul(c,mod,b);//вычисление модуля

}