A technique is provided for performing modular multiplication. In one embodiment, an apparatus in a microprocessor is provided for accomplishing modular multiplication operations. The apparatus includes translation logic and execution logic. The translation logic receives an atomic Montgomery multiplication instruction from a source therefrom, where the atomic Montgomery multiplication instruction prescribes generation of a Montgomery product. The translation logic translates the atomic Montgomery multiplication instruction into a sequence of micro instructions specifying sub-operations required to accomplish generation of the Montgomery product. The execution logic is operatively coupled to the translation logic. The execution logic receives the sequence of micro instructions, and performs the sub-operations to generate the Montgomery product.