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)
- 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
-
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}, url = {https://eprint.iacr.org/2018/1038} }