Modular multiplicative inverse: Difference between revisions

Revision as of 16:27, 22 August 2023

Revision as of 02:22, 10 September 2023

Line 116:

This method is generally slower than the extended Euclidean algorithm, but is sometimes used when an implementation for modular exponentiation is already available. Some disadvantages of this method include:

*The value <math>\phi (m)</math> must be known and the most efficient known computation requires {{mvar|m}}'s [[factorization]]. Factorization is widely believed to be a computationally hard problem. However, calculating <math>\phi (m)</math> is straightforward when the prime factorization of {{mvar|m}} is known.

*The relative cost of exponentiation. Though it can be implemented more efficiently using [[modular exponentiation]], when large values of {{mvar|m}} are involved this is most efficiently computed with the [[Montgomery reduction]] method., Thisthat algorithmmethod, itself, requiresrequiring a modular inverse mod {{mvar|m}}, which is what was to be calculated in the first place. Without the Montgomery method, the standard [[binary exponentiation]], which requires division mod {{mvar|m}} at every step, is a slow operation when {{mvar|m}} is large.

One notable ''advantage'' of this technique is that there are no conditional branches which depend on the value of {{mvar|a}}, and thus the value of {{mvar|a}}, which may be an important secret in [[public-key cryptography]], can be protected from [[side-channel attack]]s. For this reason, the standard implementation of [[Curve25519]] uses this technique to compute an inverse.