Cryptology ePrint Archive: Report 2018/985

Efficient Inversion In (Pseudo-)Mersenne Prime Order Fields

Kaushik Nath and Palash Sarkar

Abstract: Efficient scalar multiplication algorithms require a single finite field inversion at the end to convert from projective to affine coordinates. This inversion consumes a significant proportion of the total time. The present work makes a comprehensive study of inversion over Mersenne and pseudo-Mersenne prime order fields. Inversion algorithms for such primes are based on exponentiation which in turn requires efficient algorithms for multiplication, squaring and modulo reduction. From a theoretical point of view, we present a number of algorithms for multiplication/squaring and reduction leading to a number of different inversion algorithms 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, they 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 twenty 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 all the relevant inversion algorithms for a wide range of Intel processors. We were able to find previous 64-bit implementations of inversion for six of the twenty primes considered in this work. On the Haswell, Skylake and Kabylake processors of Intel, for all the six primes where previous implementations are available, our implementations outperform such previous implementations. The assembly codes that we have developed are publicly available and can be used as a plug-in to replace the inversion routines in existing softwares for scalar multiplication.

Category / Keywords: implementation / finite fields, inversion, multiplication, reduction, scalar multiplication, elliptic curves

Date: received 13 Oct 2018, last revised 5 Nov 2018

Contact author: palash at isical ac in

Available format(s): PDF | BibTeX Citation

Version: 20181106:063428 (All versions of this report)

Short URL: ia.cr/2018/985


[ Cryptology ePrint archive ]