Операция умножения является одной из наиболее трудоемких и вместе с функцией деления определяет время работы алгоритма.
Пусть неотрицательные целые числа а и b заданы в системе счисления с основанием B.
где 0 ≤ ai < B, 0 ≤ bi < B
Самый очевидный способ умножения — умножение «в столбик».
Алгоритм 2. Умножение целых чисел «в столбик», [Молдовян Н.А. и др., 2004].
Вход. Целые числа , где 0 < b ≤ a.
Выход. Произведение
1. Для i = 0, 1, ...,п- 1 положить ci= 0
2. Для i = 0, 1, ...,п- 1 выполнить следующие действия.
2.1. Для j = 0, 1, ...,п- 1:
2.1.1. Положить s= 0.
2.1.2. Вычислить t = ci+j+aibj+s, ci+j=t (mod B), .
2.2. Положить ci+n =s.
3. Результат:
Во внешнем цикле этого алгоритма вычисляются частичные произведения , а во внутреннем — произведения , где j = 0, 1, ..., п- 1. Текущий разряд произведения равен t (mod В), а очередной перенос: . При этом на шаге 2.1.2 выполняется неравенство:
Сложность умножения в «столбик» О(n2).
Функция умножения реализована как умножение с вычислением модуля.
Код функции 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 = ci+j+aiaj+s, ci+j=t (mod B), .
2.3. Положить ci+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);//вычисление модуля
}