form of the residue class with respect to is , that is, it is the representative of the residue class . For example, suppose that and that . The Montgomery forms of 3, 5, 7, and 15 are , , , and . Addition and subtraction in Montgomery form are the same as ordinary modular addition and subtraction because of the distributive law: This is a consequence of the fact that, because , multiplication by is an isomorphism on the additive group . For example, , which in Montgomery form becomes . Multiplication in Montgomery form, however, is seemingly more complicated. The usual product of and does not represent the product of and because it has an extra factor of : Computing products in Montgomery form requires removing the extra factor of . While division by is cheap, the intermediate product is not divisible by because the modulo operation has destroyed that property. So for instance, the product of the Montgomery forms of 7 and 15 modulo 17 is the product of 3 and 4, which is 12. Since 12 is not divisible by 100, additional effort is required to remove the extra factor of . Removing the extra factor of can be done by multiplying by an integer such that , that is, by an whose residue class is the modular inverse of mod . Then, working modulo , The integer exists because of the assumption that and are coprime. It can be constructed using the extended Euclidean algorithm. The extended Euclidean algorithm efficiently determines integers and that satisfy Bézout's identity: , , and: This shows that it is possible to do multiplication in Montgomery form. A straightforward algorithm to multiply numbers in Montgomery form is therefore to multiply , , and as integers and reduce modulo . For example, to multiply 7 and 15 modulo 17 in Montgomery form, again with , compute the product of 3 and 4 to get 12 as above. The extended Euclidean algorithm implies that , so . Multiply 12 by 8 to get 96 and reduce modulo 17 to get 11. This is the Montgomery form of 3, as expected. The REDC algorithm While the above algorithm is correct, it is slower than multiplication in the standard representation because of the need to multiply by and divide by . Montgomery reduction, also known as REDC, is an algorithm which simultaneously computes the