An arithmetic device for Montgomery modular multiplication which quickly calculates a parameter ND with a large number of effective lower bits. The device comprises an ND generator, a multiplication-accumulation (MAC) operator, and a sum data store. The ND generator produces effective lower bits of ND at a rate of k bits per clock cycle, with reference to lower k bits of a variable S, as well as to lower k bits of an odd positive integer N. The MAC operator multiplies the produced k-bit ND value by N and adds the resulting product to S. The sum data store stores the variable S, which is updated with the output of the MAC operator, with its bits shifted right by k bits, for use by the ND generator in the subsequent clock cycle.