Paper 2020/1497

A note on the calculation of some functions in finite fields: Tricks of the Trade

Michael Scott
Abstract

Optimization of finite field arithmetic is important for the deployment of public key cryptography, particularly in the context of elliptic curve cryptography. Until now the primary concern has been operations over the prime field $\F_p$, where $p$ is a prime. With the advent of pairing-based cryptography there arises a need to also look at optimal arithmetic over extension fields $\F_{p^n}$ for small values of $n$. Here we focus on the determination of quadratic residuosity and the calculation of inverses and square roots over these fields, operations often carried out in conjunction with one another. We demonstrate with a minor improvement in a hash-to-curve algorithm, and a major speed-up in the calculation of square roots in quadratic extensions.

Note: New application - point validation on Montgomery curves

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Preprint.
Keywords
Finite Field Arithmetic
Contact author(s)
michael scott @ tii ae
History
2023-11-18: last of 5 revisions
2020-12-02: received
See all versions
Short URL
https://ia.cr/2020/1497
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/1497,
      author = {Michael Scott},
      title = {A note on the calculation of some functions in finite fields: Tricks of the Trade},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1497},
      year = {2020},
      note = {\url{https://eprint.iacr.org/2020/1497}},
      url = {https://eprint.iacr.org/2020/1497}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.