Techniques are disclosed for utilizing a block Montgomery machine designed only to operate at a fixed block length to perform operations using non-block length (flexible)moduli. In one embodiment, a new modulus n′ is obtained having a block length equal to the fixed block length of the Montgomery machine or a multiple thereof. At least one modular additive operation is performed with the new modulus n′, and at least one modular multiplicative operation is performed with the non-block length modulus n. In this way, the result of the at least one additive operation is sufficiently reduced when a carry stems from the additive operation.