<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

Pubblicato online: 14 dic 2018

Pagine: 400 - 402

Ricevuto: 16 ott 2017

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

Parole chiave
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

Pubblicato online: 14 dic 2018

Pagine: 400 - 402

Ricevuto: 16 ott 2017

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

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

Parole chiave
finite fields, multiplicative inverses