Cryptology ePrint Archive: Report 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.

Category / Keywords: implementation / Finite Field Arithmetic

Date: received 30 Nov 2020, last revised 8 Dec 2020

Contact author: michael scott at tii ae

Available format(s): PDF | BibTeX Citation

Version: 20201208:140307 (All versions of this report)

Short URL: ia.cr/2020/1497


[ Cryptology ePrint archive ]