Welcome to the resource topic for 2018/1038
Title:
On inversion modulo pseudo-Mersenne primes
Authors: 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.
ePrint: https://eprint.iacr.org/2018/1038
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .