I suppose I already suggested that one computes a^{-1} mod b as a^{b-1} mod b, using a plain old modexp. I realise that this will be asymptotically slower, in this setting O(n^3) vs O(n^2), but it ought have a much lower constant factor. Torbjörn