Protected division Method

___________________________________________
Input: a = ( 0, am-1 , …, a0 )
b = ( bn-1 , …, b0 ) A = ( 0, am-1 , …, am-n+1 )
Output: q = a div b and r = a mod b
___________________________________________
_’ _ 1; _ _ 1; _ _ 1;
for j = 1 to (m – n + 1) do
a _ SHLm+1(a , 1)
_ _ carry ; _ ___ _ _
daddr _ baddr + _ (caddr - baddr )
d _ CPL2n (d)
A _ ADDn (A , b)
_ _ (_ _ _’ ) _ (_ _ carry) _ (_’ _ carry)
_ _ _ _’ ; _ _ _ _ _ ; _’ _ _
LSB(a) = _
end for
if (_ _) then b _ CPL2n (b)
if (_ _) then c _ CPL2n (c)
if (_ _) then A _ ADDn (A , b)

/* Shift */

/* 2’s complement*/

/* Addition*/

/* Final Correction*/

Previous slide Next slide Back to first slide View graphic version

Notes:

Alpha contains the carry as before

Delta indicates the usage of variable Baddr or Caddr for the 2’s complement operation (gamma = 1 : use Caddr, gamma=0 : use Baddr)

Alpha’ is the old value of Alpha (contains 0 if correction required)