- What is the degree of
*q*_{2}? Give an estimation for*D*(*n*). - Assume now that
*n*is a power of 2, say*n*= 2^{k}. We run the Euclidean Algorithm starting from*r*_{0},*r*_{1}. Assume that the degree of each remainder*r*_{i+1}is half the degree of the previous remainder*r*_{i}. Is the Euclidean Algorithm faster in this special case than in the usual one? In other words, does the time complexity of the Euclidean Algorithm becomes sub-quadratic, i.e.*O*(*n*^{}) for some < 2?

2006-01-09