Proof and Improvement of Shantz’s Modular Division and Lórencz’s Modular Inverse Algorithms

Abstract

Modular division or inverse is fundamental in finite field arithmetic, and it widely exists in cryptosystems like elliptic curve cryptography. Shantz’s algorithm can be easily used for modular division in addition to the plus and minus methods. Nevertheless, a proof of the algorithm is in lack in the literature so far. This work presents a proof of Shantz’s algorithm by matrix transforms. Also, Lórencz’s modular inverse algorithm is innovative in applying left-shift operations, for which an analysis and an improvement are also given in this paper.