Paper 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.

Note: New method based on Scholz-Brauer conjecture. More discussion. New short Appendix added. Typo in Algorithm 1 line 27 fixed

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Preprint. MINOR revision.
Keywords
Elliptic curves
Contact author(s)
mscott @ indigo ie
History
2020-07-16: last of 7 revisions
2018-10-30: received
See all versions
Short URL
https://ia.cr/2018/1038
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/1038,
      author = {Michael Scott},
      title = {On inversion modulo pseudo-Mersenne primes},
      howpublished = {Cryptology ePrint Archive, Paper 2018/1038},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/1038}},
      url = {https://eprint.iacr.org/2018/1038}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.