модулярное умножение...

  • Автор темы Guest
  • Дата начала
G

Guest

#1
очень нужно реализовать алгоритм модулярного умножения,у меня есть псевдокод, я не знаю как его перевести,а нужно перести в C++,но у меня есть наметки,что я немного понимаю.Сам псевдокод вот как выглядит
m_shifts:=0;
while n[m_shifts]=0 do
begin
shift_left(N and A);
m_shifts:=m_shifts+1;
end;
m:=m_shifts;
reset(P);
n_short:=N[m];
for i:= down to 1 do
begin
shift_left(P):{сдвиг на 1 элемент влево или умножение P*r}
if b<>0 then
addk(A*B,{to}P);
let p_short represent the 2 high assimilated digits of P;
k:=abs(p_short)div n_short;
if p_short-k*n_short>n_short div 2 then k:=k+1;
if k>0 then
begin
if p_short<0 then
addk(k*N,{to}P)
else
addk(-k*N,{to}P);
end;
end;{for}
right shift P,N by m_shifts;
if P<0 then
P:=P+N;
white(P); {P - результат}
Псевдокод P+k*N (процедуры addk) тож имеется
carry:=0;
for i:=1 to m do
begin
t:=P+k*N+carry;
P:=t mod r;
carry:=t div r;
end;
P[m+1]:=carry;
write(P);{P-результат}
Я перевела вот что... и то не уверена...
void addk(_______)
{
int carry = 0, t;
for (int i = 0; i < m; i++)
{
t = P + k * N + carry;
P = t % r;
carry = t / r;
}
P[m + 1] = carry;
}

void P()
{
int m_shifts = 0;
while (n[m_shifts] == 0)
{
shift_left(N & A);
m_shifts++;
}
m = m_shifts;
reset(P) - не знаю че такое
n_short = N[m];
for (int i = n; i > 0; i--)
{
shift_left(P);
if (b != 0)
addk(______);
let.... - тоже не знаю че за строчка
k = abs(p_short) / n_short;
if (p_short - k*n_short > n_short / 2)
k++;
if (k > 0)
{
if (p_short < 0)
{
addk(_____);
}
else
{
addk(_____);
}
}
}
//right shift P, N by m_shift - тоже не знаю что
if (P < 0)
P += N;
}
Этот алгоритм взят из книги Казарина,глава 2,если что. Помогите пожалуйста....