[atq2119]

That's a pretty snarky and unhelpful approach to the conversation.

That said, I'm also a bit surprised to see somebody discuss modular inverses without mentioning the extended euclidean algorithm, which is a more elementary solution.

[cperciva]

Snarky I'll admit, but it was a serious question. Inverse is quasilinear time; the exponential is quasiquadratic. Maybe he didn't know about the EEA?

[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.

[benreesman]

I disagree on two counts:

- having Colin stop by your thread is strictly an opportunity for useful information to flow from a singular source to many people

- you would hear that aloud 100 times a day in any office where serious work was being done by professionals on a deadline and think nothing of it, bet your ass places in the world where serious hackers rise only on merit and have the best gear embargoed are saying stuff like that all the time. this nepotism capture bubble is an outlier in the history of serious engineering.

Defining the rudeness threshold down to the point where cperciva clears it is one part comedy and two parts tragedy with the words Hacker News in bold at the top of the page.