  We generalize the concept of reduced Arakelov divisors and define $C$-reduced
divisors for a given number $C \geq 1$. These $C$-reduced divisors have
remarkable properties which are similar to the properties of reduced ones. In
this paper, we describe an algorithm to test whether an Arakelov divisor of a
real quadratic field $F$ is $C$-reduced in time polynomial in $\log|\Delta_F|$
with $\Delta_F$ the discriminant of $F$. Moreover, we give an example of a
cubic field for which our algorithm does not work.
