For the question, we write $\ell(a)$ to denote the length of the positive integer $a=(a_1\cdots a_k)_2$.
In my cryptography textbook, in the section of binary division, I found the following claim:
Let $a\geq b\in \Bbb{Z}^+$. Then, the binary division $a:b$ requires $\leq \ell(b)\cdot(\ell(a)-\ell(b)+1)$ binary bit operations.
Τhen, in order to prove the claim, it continues:
From the division algorithm, $\exists \ a,b\in \Bbb{Z}^+: a=bq+r,\ 0\leq r<b.$ And from an easy to prove theorem, we know that $\ell (q) \leq\ell(a)-\ell(b)+1.$
Now, finding the quotient and remainder requires $\ell(q)\leq \ell(a)-\ell(b)+1$ subtractions. subtractions.
Each subtraction requires $\ell (b)$ bit operations.
And in this sentence above I faced the problem.
Why do we have $\ell(b)$ bit operations instead of $\ell(a)$?
For example:
In this example we have $2$ subtractions. In the first $(1101-1001)$ we have $4=\ell(b)$ binary bits operations. But, in the second $(10001-1001)$ we have $5>\ell(b)=4$ binary bits operations.
Why does this happen? Do I misunderstand something?
Thank you.
