# Euclidean algorithm: the number gets smaller with complexity log(k)

• Oct 31st 2013, 12:05 PM
huberscher
Euclidean algorithm: the number gets smaller with complexity log(k)
Hi there

Given the exercise

Let $\displaystyle 1 \le d \in \mathbb{N} , k=f*d+h , h<f$.

Firstly show that the variable h has (with respect to basis 2) less digits than k. Then conclude that the euclidean algorithm is (ends) in polynomial time in $\displaystyle log_2(k)$.

I don't find a meaningful beginning. I can write $\displaystyle k=k_{d_k} k_{d_k-1} ... k_1 k_0 \text{ while } k_i \in \{0,1\} \forall i$ as a representation of k in the dual System. Then

$\displaystyle k=k_{d_k} k_{d_k-1} ... k_1 k_0 = \underbrace{f_{d_f} ... f_0}_{=f} * \underbrace{d_{d_d} ... d_0}_{=d} + \underbrace{h_{d_h} ... h_0}_{=h}$

Ok that far. Now what is here the idea? I don't see a track honestly ...

Regards
• Oct 31st 2013, 12:14 PM
SlipEternal
Re: Euclidean algorithm: the number gets smaller with complexity log(k)
Edit:

Do you also have $\displaystyle 0\le h < f$?
• Oct 31st 2013, 12:25 PM
huberscher
Re: Euclidean algorithm: the number gets smaller with complexity log(k)
Well it's not written on the exercise sheet but I think we can assume that all those numbers are non-negative integers...
• Oct 31st 2013, 01:20 PM
SlipEternal
Re: Euclidean algorithm: the number gets smaller with complexity log(k)
You have $\displaystyle h < f = \dfrac{k-h}{d}$. So, $\displaystyle h(d+1) < k$. This implies that $\displaystyle h < \dfrac{k}{d+1} \le \dfrac{k}{1+1} = \dfrac{k}{2}$. If $\displaystyle k$ has $\displaystyle n$ digits, then $\displaystyle k < 2^n$. So, since $\displaystyle h < \dfrac{k}{2}$, it must be that $\displaystyle h < \dfrac{k}{2} < 2^{n-1}$, implying $\displaystyle h$ has at most $\displaystyle n-1$ digits.