Операцию умножения по модулю можно выполнять следующим образом. Если А и В < Р, то С = (А Ч В) (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);

}