The Calcualtion of Multiplicative Inverses Over GF(P) Efficiently Where P is a Mersenne Prime
- 1 May 1986
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-35 (5), 478-482
- https://doi.org/10.1109/TC.1986.1676791
Abstract
The extended Euclidean algorithm is typically used to calculate multiplicative inverses over finite fields and rings of integers. The algorithm presented here has approximately the same number of average iterations and maximum number of iterations. It is shown, when P is a Mersenne prime, implementation of this algorithm on a processor, designed especially for mod P arithmetic operations, produces a more efficient algorithm with respect to the amount of program statements and number of operations. It is then shown heuristically, when the division and multiplications are performed simultaneously, the Euclidean algorithm has fewer subiterations.Keywords
This publication has 9 references indexed in Scilit:
- The design of specialized residue classes for efficient recursive digital filter realizationIEEE Transactions on Acoustics, Speech, and Signal Processing, 1982
- A high-speed low-cost recursive digital filter using residue number arithmeticProceedings of the IEEE, 1977
- The use of residue number systems in the design of finite impulse response digital filtersIEEE Transactions on Circuits and Systems, 1977
- Number theoretic transforms to implement fast digital convolutionProceedings of the IEEE, 1975
- The use of finite fields to compute convolutionsIEEE Transactions on Information Theory, 1975
- The Computing Time of the Euclidean AlgorithmSIAM Journal on Computing, 1974
- On Euclid's Algorithm and the Computation of Polynomial Greatest Common DivisorsJournal of the ACM, 1971
- On Euclid's Algorithm and the Theory of SubresultantsJournal of the ACM, 1971
- Computing Multiplicative Inverses in GF(p)Mathematics of Computation, 1969