Cryptology ePrint Archive: Report 2018/1038

On inversion modulo pseudo-Mersenne primes

Michael Scott

Abstract: It is well established that the method of choice for implementing a side-channel secure modular inversion, is to use Fermat's little theorem. So $1/x = x^{p-2} \bmod p$. This can be calculated using any multiply-and-square method safe in the knowledge that no branching or indexing with potentially secret data (such as $x$) will be required. However in the case where the modulus $p$ is a pseudo-Mersenne, or Mersenne, prime of the form $p=2^n-c$, where $c$ is small, this process can be optimized to greatly reduce the number of multiplications required. Unfortunately an optimal solution must it appears be tailored specifically depending on $n$ and $c$. What appears to be missing from the literature is a near-optimal heuristic method that works reasonably well in all cases.

Category / Keywords: implementation / Elliptic curves

Date: received 25 Oct 2018, last revised 6 Jan 2020

Contact author: mscott at indigo ie

Available format(s): PDF | BibTeX Citation

Note: New method based on Scholz-Brauer conjecture. More discussion. New short Appendix added.

Version: 20200106:121738 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]