Page 123 - Hardware Implementation of Finite-Field Arithmetic

106 Cha pte r F o u r

will remain included between −p and p, so that they can be represented
as (k + 1)-bit 2’s complement numbers. A final correction step is
necessary if c < 0.
Algorithm 4.5—mod p division, plus-minus algorithm

a := p; b := y; c := 0; d := x; alpha := k; beta := k;
while beta > 0 loop
if b mod 4 = 0 then
b := b/4; d := divide_by_4(d, p); beta := beta - 2;
elsif b mod 2 = 0 then
b := b/2; d := divide_by_2(d, p); beta := beta - 1;
else
old_b := b; old_d := d; old_alpha := alpha;
old_beta := beta;
if (b+a) mod 4 = 0 then
b := (b+a)/4; d := divide_by_4(d+c, p);
else
b := (b-a)/4; d := divide_by_4(d-c, p);
end if;
if beta < alpha then a := old_b; c := old_d;
alpha := old_beta; beta := old_alpha - 1;
else beta := beta - 1;
end if;
end if;
end loop;
if c < 0 then c := c + p; end if;
if a = 1 then z := c; else z := p-c; end if;
In order to avoid the comparison of α and β , an alternative
i i
method consists of updating at each step
dif =β − α and min = min(α , β ) (4.32)
i i i i i i
Algorithm 4.6—mod p division, plus-minus algorithm, second version

a := p; b := y; c := 0; d := x; dif := 0; min := k;
while min > 0 loop
if b mod 4 = 0 then
b := b/4; d := divide_by_4(d, p);
if dif <= 0 then min := min - 2;
elsif dif = 1 then min := min - 1;
end if;
dif := dif - 2;
elsif b mod 2 = 0 then
b := b/2; d := divide_by_2(d, p);
if dif <= 0 then min := min - 1; end if;
dif := dif - 1;
else
old_b := b; old_d := d;
if (b+a) mod 4 = 0 then
b := (b+a)/4; d := divide_by_4(d+c, p);
else