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

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)