Computing multiplicative inverses in
Abstract: Two familiar algorithms, the extended Euclidean algorithm and the Fermat algorithm (based on Fermat's theorem ), are analyzed and compared as methods for computing multiplicative inverses in . Using Knuth's results on the average number of divisions in the Euclidean algorithm, it is shown that the average number of arithmetic operations required by the Fermat algorithm is nearly twice as large as the average number for the extended Euclidean algorithm. For each of the two algorithms, forward and backward versions are distinguished. It is shown that all numbers computed in the forward extended Euclidean algorithm are bounded by the larger of the two inputs, a property which was previously established by Kelisky for the backward version.
-  I. Borosh and A. S. Fraenkel, Exact solutions of linear equations with rational coefficients by congruence techniques, Math. Comp. 20 (1966), 107–112. MR 0187379, https://doi.org/10.1090/S0025-5718-1966-0187379-1
-  George E. Collins, Subresultants and reduced polynomial remainder sequences, J. Assoc. Comput. Mach. 14 (1967), 128–142. MR 0215512, https://doi.org/10.1145/321371.321381
-  R. P. Kelisky, Concerning the Euclidean algorithm, Fibonacci Quart. 3 (1965), 219–223. MR 0188139
-  Donald E. Knuth, The art of computer programming, 2nd ed., Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1975. Volume 1: Fundamental algorithms; Addison-Wesley Series in Computer Science and Information Processing. MR 0378456
-  H. Takahasi & Y. Ishibashi, ``A new method for 'exact calculation' by a digital computer,'' Information Processing in Japan, v. 1, 1961, pp. 28-42.
-  J. V. Uspenshy & M. A. Heaslet, Elementary Number Theory, McGraw-Hill, New York, 1939. MR 1, 38.
- I. Borosh & A. S. Fraenkel, ``Exact solutions of linear equations with rational coefficients by congruence techniques,'' Math. Comp., v. 20, 1966, pp. 107-112. MR 32 #4831. MR 0187379 (32:4831)
- G. E. Collins, ``Subresultants and reduced polynomial remainder sequences,'' J. Assoc. Comput. Mach., v. 14, 1967, pp. 128-142. MR 35 #6352. MR 0215512 (35:6352)
- R. P. Kelisky, ``Concerning the Euclidean algorithm,'' Fibonacci Quart., v. 3, 1965, pp. 219-223. MR 32 #5579. MR 0188139 (32:5579)
- D. E. Knuth, The Art of Computer Programming. Vol. 1: Fundamental Algorithms, AddisonWesley, Reading, Mass., 1968. MR 0378456 (51:14624)
- H. Takahasi & Y. Ishibashi, ``A new method for 'exact calculation' by a digital computer,'' Information Processing in Japan, v. 1, 1961, pp. 28-42.
- J. V. Uspenshy & M. A. Heaslet, Elementary Number Theory, McGraw-Hill, New York, 1939. MR 1, 38.
Retrieve articles in Mathematics of Computation with MSC: 65.10
Retrieve articles in all journals with MSC: 65.10