Efficient algorithms for remainder computation and exponentiation of long numbers (Q1364066)

The author discusses three different algorithms for computing the remainder \(W \bmod M\), where \(W\) is a \(2n\)-word integer and \(M\) is an \(n\)-word integer. (Words consist of a number of \(p\) bits dependent on the configuration of the CPU). The complexity of the three algorithms is estimated in terms of \(T_a\) the execution time for addition of two \(n\)-word integers, \(T_m\) the execution time for multiplication of two \(n\)-word integers into a \(2n\)-word integer and \(T_d\) the execution time for dividing a \(2n\)-word integer by an \(n\)-word integer, producing an \(n\)-word quotient. The author claims to have studied the exponentiation of long numbers and refers to \textit{D. Knuth}'s book [The art of computer programming. Vol. 1 (1968; Zbl 0191.17903)]. He gives a table with the number of computations to be made for different lengths of the exponents when the methods of Knuth are used. He fails to explain what the real strength of the Montgomery method is. For exponentiation of long numbers, there exist faster methods (e.g., using addition chains that can be found in an impressive number of publications) than those described by Knuth.