I have not followed this thread, but would something akin to Jebelean's bidirectional exact division algorithm work for sqrt_exact? (We have Jebelean's algorithm for divexact implemented in mpn/generic/divexact.c but it is disabled as I never got around to testing it properly.) -- Torbjörn Please encrypt, key id 0xC8601622