Paper 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.
Metadata
- Available format(s)
- Category
- Implementation
- Publication info
- Preprint. MINOR revision.
- Keywords
- finite fieldsinversionmultiplicationreductionscalar multiplicationelliptic curves
- Contact author(s)
- palash @ isical ac in
- History
- 2020-01-07: last of 3 revisions
- 2018-10-18: received
- See all versions
- Short URL
- https://ia.cr/2018/985
- License
-
CC BY