Cryptology ePrint Archive: Report 2018/985

Efficient Arithmetic In (Pseudo-)Mersenne Prime Order Fields

Kaushik Nath and Palash Sarkar

Abstract: Elliptic curve cryptography requires efficient arithmetic over the underlying field. In particular, fast implementation of multiplication and squaring over the finite field is required for efficient projective coordinate based scalar multiplication as well as for inversion using Fermatís little theorem. In the present work we consider the problem of obtaining efficient algorithms for field multiplication and squaring. From a theoretical point of view, we present a number of algorithms for multiplication/squaring and reduction which are appropriate for different settings. Our algorithms collect together and generalise ideas which are scattered across various papers and codes. At the same time, we also introduce new ideas to improve upon existing works. A key theoretical feature of our work, which is not present in previous works, is that we provide formal statements and detailed proofs of correctness of the different reduction algorithms that we describe. On the implementation aspect, a total of fourteen primes are considered, covering all previously proposed cryptographically relevant (pseudo-)Mersenne prime order fields at various security levels. For each of these fields, we provide 64-bit assembly implementations of the relevant multiplication and squaring algorithms targeted towards two different modern Intel architectures. We were able to find previous 64-bit implementations for six of the fourteen primes considered in this work. On the Haswell and Skylake processors of Intel, for all the six primes where previous implementations are available, our implementations outperform such previous implementations.

Category / Keywords: implementation / field multiplication, field squaring, reduction, inversion, constant-time computation, Fermatís little theorem, elliptic curve cryptography, scalar multiplication

Date: received 13 Oct 2018, last revised 7 Jan 2020

Contact author: kaushikn_r at isical ac in,palash@isical ac in

Available format(s): PDF | BibTeX Citation

Note: Minor corrections.

Version: 20200107:101316 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]