value of , which may be an important secret in public-key cryptography, can be protected from side-channel attacks. For this reason, the standard implementation of Curve25519 uses this technique to compute an inverse. Multiple inverses It is possible to compute the inverse of multiple numbers , modulo a common , with a single invocation of the Euclidean algorithm and three multiplications per additional input. The basic idea is to form the product of all the , invert that, then multiply by for all to leave only the desired . More specifically, the algorithm is (all arithmetic performed modulo ): Compute the prefix products for all . Compute using any available algorithm. For from down to 2, compute and . Finally, . It is possible to perform the multiplications in a tree structure rather than linearly to exploit parallel computing. Applications Finding a modular multiplicative inverse has many applications in algorithms that rely on the theory of modular arithmetic. For instance, in cryptography the use of modular arithmetic permits some operations to be carried out more quickly and with fewer storage requirements, while other operations become more difficult. Both of these features can be used to advantage. In particular, in the RSA algorithm, encrypting and decrypting a message is done using a pair of numbers that are multiplicative inverses with respect to a carefully selected modulus. One of these numbers is made public and can be used in a rapid encryption procedure, while the other, used in the decryption procedure, is kept hidden. Determining the hidden number from the public number is considered to be computationally infeasible and this is what makes the system work to ensure privacy. As another example in a different context, consider the exact division problem in computer science where you have a list of odd word-sized numbers each divisible by and you wish to divide them all by . One solution is as follows: Use the extended Euclidean algorithm to compute , the modular multiplicative inverse of , where is the number of bits in a word. This inverse will exist since the numbers are odd and the modulus has no odd factors. For each number in the list, multiply it by and take the least significant word of the result. On many machines, particularly those without hardware support for division, division is a slower operation than multiplication, so this approach can yield a considerable speedup.