# Complexity of Boudot's zero-knowledge range proof scheme

According to Camenisch et al. in Efficient Protocols for Set Membership and Range Proofs (see Section 1.2), the range proofs devised by Boudot in Effcient Proofs that a Committed Number Lies in an Interval are based on representing a number as the sum of four squares.

Based on this, Camenisch et al. claim that the complexity of Boudot's scheme is governed by the cost of finding these squares (see Section 4.4 of the paper by Camenisch et al.)

However, studying Boudot's schemes, I do not see any reference to this issue. Rather, Boudot defines the squares involved in the proof as $\tilde{x}^2_1,\bar{x}^2_1$, where $\tilde{x_1} = \lfloor\sqrt{x-a}\rfloor$ and $\bar{x_1} = \lfloor\sqrt{b-x}\rfloor$, where the value being proved, $x$, belongs in $[a,b]$. So the computation of these squares seems quite straight forward.

What am I missing?