  We obtain new complexity bounds for computing a triangular integral basis of
a number field or a function field. We reach for function fields a softly
linear cost with respect to the size of the output when the residual
characteristic is zero or big enough. Analogous results are obtained for
integral basis of fractional ideals, key ingredients towards fast computation
of Riemann-Roch spaces. The proof is based on the recent fast OM algorithm of
the authors and on the MaxMin algorithm of Stainsby, together with optimal
truncation bounds and a precise complexity analysis.
