Computing multiplicative inverses in finite fields by long division
Otokar Grošek, Tomáš Fabšič · Journal of Electrical Engineering · 2018
Abstract We study a method of computing multiplicative inverses in finite fields using long division. In the case of fields of a prime order p , we construct one fixed integer d ( p ) with the property that for any nonzero field element a , we can compute its inverse by dividing d ( p ) by a and by reducing the result modulo p . We show how to construct the smallest d ( p ) with this property. We demonstrate that a similar approach works in finite fields of a non-prime order, as well. However, we demonstrate that the studied method (in both cases) has worse asymptotic complexity than the extended Euclidean algorithm.