Let $1<a<b<N$, $1<N$ is integer. SHOW that at most $2 \log _2a$ additions (mod $N$) are needed to compute the multiplication $ab$ (mod $N$). hint : you may use "double and add method" of multiplication which is an analogue of square and multiply method.

what i have done is that let $2^{k-1}$ $_=^ <N<2^k$, $a=2^k -1$ because in double and add method, many 1 makes more additions. and if all of binary digit is 1, it means that maximum addition for some digit's number. $a=2^k -1$ will makes maximum addition. but, i think that in multiplication of $ab$(mod $N$), the maximum number of additions are at most $k-1<$$ \log _2a$. when $a=(11)_{(2)}$, $a*b=(2b)+b$.(one addition), when $ a=(111)_{(2)}$, $a*b=2((2b)+b)+b$.(two addition)

i don't know wheter my idea is right. and i guess that coefficient'$2$' in $2 \log _2a$ is related with mod $N$ because i don't use modulus.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.