[tmyklebu]

Well, modular multiplication is faster than modular inverse, both asymptotically for large moduli and practically for almost all moduli I can think of. (2, 3, and 4 being notable exceptions!)

The article computes modular inverses of a_1, ..., a_n by:

- Computing (a_1 * ... * a_i) = (a_1 * ... * a_{i-1}) * a_i recursively

- Computing (a_1 * ... * a_n)^(-1) by square-and-multiply

- Computing (a_1 * ... * a_i)^(-1) = (a_1 * ... * a_{i+1})^(-1) a_{i+1} recursively.

- Computing a_i^(-1) = (a_1 * ... * a_i)^(-1) * (a_1 * ... * a_{i-1}) for each i.

The second step is a scalar operation, so its running time is immaterial as long as you aren't doing something too silly.

For my caveman brain, both Fermat's little theorem and square-and-multiply exponentiation are pretty easy to understand. Moreover, the code is going to be "defect-evident"---if I've gotten the logic wrong or forgotten integer promotions or modular reductions as in qsort's post, it'll quickly be clear by skimming the code.