Сайт о программировании, математике и моделировании
Программа, реализующая модулярное умножение
Операцию умножения по модулю можно выполнять следующим образом. Если А и В < Р, то С = (А Ч В) (mod P) вычисляется так:
D:=A Ч B;
С := D mod P.
Умножение длинных чисел по модулю: С=(А*В) mod P
void MulMod(
DIGIT C[ ], /* результат */
const DIGIT A[ ], /* первый сомножитель */
const DIGIT B[ ], /* второй сомножитель */
const DIGIT P[ ], /* модуль */
int n) /* длина чисел */
{
DIGIT D[MAX_SIZE*2];
Mul (D, А, В, n);
Div (D, P, NULL, C, 2*n, n);
}
Аналогичным образом выполняется вычисление квадрата по модулю, С = A2 (mod P) вычисляется так:
D := А2;
С := D mod P.
Вычисление квадрата длинного числа по модулю: С=А2 mod P
void SquareMod(
DIGIT С[ ], /* результат */
const DIGIT A[ ], /* основание степени */
const DIGIT P[ ], /* модуль */
int n) /* длина чисел */
{
DIGIT D[MAX_SIZE*2];
SquareTri (D, A, n);
Div (D, P, NULL, C, 2*n, n);
}
Для операции Монтгомери существует оптимизированный алгоритм, не требующий деления в поле GF(P), которое бы существенно замедлило вычисления. Ниже приведен текст программы, реализующей этот алгоритм. Умножение Монтгомери длинных чисел: S=(KoL) mod P */
void MulMont(
DIGIT S[ ], /* результат */
const DIGIT K[ ], /* первый сомножитель */
const DIGIT L[ ], /* второй сомножитель */
const DIGIT P[ ], /* модуль */
DIGIT z, /* -Po-1 (mod b) */
int n) /* длина чисел */
{
int j, i;
DIGIT T[MAX_SIZE+1];
TWODIGIT ulTmp;
DIGIT uiTmp, e;
Zero (T, n+1); /* T = 0 */
for (i=0; i<n; i++)
{ /* T += К * L|i| */
ulTmp = 0;
uiTmp = L[i];
for (j=0; j<n; j++)
{ ulTmp = (TWODIGIT)K[j] * uiTmp +
(TWODIGIT)HIDIGIT (ulTmp) + (TWODIGIT)T(j]; T[j] T[j]= LODIGIT (ulTmp);
}
T[n] += HIDIGIT (uITmp);
e = T[0]*z;
/* Т += е * Р и сдвиг влево */
uITmp = (TWODIGIT)e*P[0] + (TWODIGIT)T[0];
for(j=l;j<n;j++)
{ uITmp = (TWODIGIT)e * P[j] +
(TWODIGIT)HIDIGIT (uITmp) + (TWODIGIT)T[j];
T[j-1] = LODIGIT (uITmp);
}
uITmp = (TWODIGIT)HIDIGIT (uITmp) + (TWODIGIT)T[n];
T[n-1] = LODIGIT (uITmp);
T[n] = HIDIGIT (uITmp);
}
if(T[n]) /*S>=P*/
Sub (T, T, P, n);
while (Cmp (T, P, n) >=0) /* S>=P */
Sub (T, T, P, n);
Assign (S, T, n);
}
Print article | This entry was posted by root on 09.08.2012 at 8:27 пп, and is filed under Задачи и решения. Follow any responses to this post through RSS 2.0. Вы можете оставить комментарий или трэкбэк с вашего сайта. |
2 года назад
Спасибо! Ваш посетитель !
2 года назад
очень огромное спасибо за программу!
2 года назад
Привет администрация progrm.ru !
Мне всего 13 лет. Несмотря на это смог реализовать перемножение больших чисел благодаря вашему сайту! Спасибо!
2 года назад
Спасибо! Ваш посетитель !
9 месяцев назад
Сайт узконаправленный , специалисты найдут необходимую информацию. Владимир.