[johndough]

> Expensive in finite field arithmetic means much more expensive than addition and multiplication.

Thanks!

> Anyway, the sqrt here is not in terms of a specific operation, but the asymptotic cost of a particular algorithm (as in, algorithm X takes sqrt N steps)

Yes, I am aware. I wanted to understand the side-tracked question anyway.