Complexity of Boudot's zero-knowledge range proof scheme
Boudot's protocol is not based on the four-square decomposition - in fact, he was the first to come up with this idea of using a decomposition in four squares, but this was only mentioned orally in the talk he gave on this paper (as I was told by people who saw it - I do not think there is any written record). The first written record on this four squares idea is Lipmaa's Asiacrypt'03 paper (where you'll find additional discussion on the cost of finding these four squares). Boudot's original protocol has other efficiency shortcoming, though, but they are related to the communication required for the protocol, not to the cost of finding the decomposition.