<p>A remainder multiplication processing device that uses a remainder multiplier and processes a remainder multiplication of data that exceeds the bit length that can be dealt with by the remainder multiplier. In the remainder multiplication processing device, the data to be remainder multiplied is split in accordance with the bit length that can be dealt with by the remainder multiplier (113). Data that have been made by use of an output result of the remainder multiplier (113) and that are required for the calculation of the remainder multiplication are stored into a storage device (123). In order to minimize the storage-area usage amount, temporary data are sequentially accumulated into a particular storage area. The temporary data accumulated in the storage area are combined to produce a solution of the remainder multiplication exceeding the bit length that can be dealt with by the remainder multiplier (113).</p>