A Montgomery multiplication apparatus (MMA), for multiplying two multiplicands modulo a predefined number, includes a pre-compute circuit and a Montgomery multiplication circuit. The pre-compute circuit is configured to compute a Montgomery pre-compute value by performing a series of iterations. In a given iteration, the pre-compute circuit is configured to modify one or more intermediate values by performing bit-wise operations on the intermediate values calculated in a preceding iteration. The Montgomery multiplication circuit is configured to multiply the two multiplicands, modulo the predefined number, by performing a plurality of Montgomery reduction operations using the Montgomery pre-compute value computed by the pre-compute circuit.