We implemented https://eprint.iacr.org/2018/623.pdf algorithm 4 (long division) for `g^q`. Algorithm 5 is the next candidate to replace algorithm 4 with possible better trade-off. It is implemented for example in https://github.com/poanetwork/vdf