<abstract xmlns="http://www.w3.org/1999/xhtml"><p>We study a method of computing multiplicative inverses in finite fields using long division. In the case of fields of a prime order <italic>p</italic>, we construct one fixed integer <italic>d</italic>(<italic>p</italic>) with the property that for any nonzero field element <italic>a</italic>, we can compute its inverse by dividing <italic>d</italic>(<italic>p</italic>) by <italic>a</italic> and by reducing the result modulo <italic>p</italic>. We show how to construct the smallest <italic>d</italic>(<italic>p</italic>) 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.</p></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.

Computing multiplicative inverses in finite fields by long division

Faculty of Electrical Engineering and Information Technology

Slovak University of Technology in Bratislava

Journal of Electrical Engineering

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

{"article-title":"Computing multiplicative inverses in finite fields by long division"}

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...

Computing multiplicative inverses in finite fields by long division

Publié en ligne: 14 déc. 2018

Pages: 400 - 402

Reçu: 16 oct. 2017

DOI: https://doi.org/10.2478/jee-2018-0059

Mots clés
finite fields, multiplicative inverses

© 2018 Otokar Grošek et al., published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

Computing multiplicative inverses in finite fields by long division

Publié en ligne: 14 déc. 2018

Pages: 400 - 402

Reçu: 16 oct. 2017

DOI: https://doi.org/10.2478/jee-2018-0059

Mots clésfinite fields, multiplicative inverses

© 2018 Otokar Grošek et al., published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

Mots clés
finite fields, multiplicative inverses