using the extended Euclidean algorithm. The Euclidean algorithm determines the greatest common divisor (gcd) of two integers, say and . If has a multiplicative inverse modulo , this gcd must be 1. The last of several equations produced by the algorithm may be solved for this gcd. Then, using a method called "back substitution", an expression connecting the original parameters and this gcd can be obtained. In other words, integers and can be found to satisfy Bézout's identity, Rewritten, this is that is, so, a modular multiplicative inverse of has been calculated. A more efficient version of the algorithm is the extended Euclidean algorithm, which, by using auxiliary equations, reduces two passes through the algorithm (back substitution can be thought of as passing through the algorithm in reverse) to just one. In big O notation, this algorithm runs in time , assuming , and is considered to be very fast and generally more efficient than its alternative, exponentiation. Using Euler's theorem As an alternative to the extended Euclidean algorithm, Euler's theorem may be used to compute modular inverses. According to Euler's theorem, if is coprime to , that is, , then where is Euler's totient function. This follows from the fact that belongs to the multiplicative group × if and only if is coprime to . Therefore, a modular multiplicative inverse can be found directly: In the special case where is a prime, and a modular inverse is given by 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 must be known and the most efficient known computation requires 's factorization. Factorization is widely believed to be a computationally hard problem. However, calculating is straightforward when the prime factorization of is known. The relative cost of exponentiation. Though it can be implemented more efficiently using modular exponentiation, when large values of are involved this is most efficiently computed with the Montgomery reduction method. This algorithm itself requires a modular inverse mod , which is what was to be calculated in the first place. Without the Montgomery method, the standard binary exponentiation, which requires division mod at every step, is a slow operation when is large. One notable advantage'' of this technique is that there are no conditional branches which depend on the value of , and thus the