To reduce the size of a surplus computing device and to provide a technique to conduct fast surplus computations.

The value of integer M, value of integer N and value of natural number (m) are inputted. In a subtracting means, the value of the integer N is set and an inputted value and the value of the integer N are compared. When the inputted value is equal to or larger than the value of the integer N, the value of the integer is subtracted from the inputted value and the subtracted value is outputted. When the inputted value is less than the value of the integer N, the inputted value is outputted. In an multiplying means, the value of the integer M is inputted as an initial value, the output value from the subtracting means is inputted, the inputted value is doubled and outputted to the subtracting means. In a counter, a counter value is incremented every time the output of the multiplying means is inputted into the subtracting means. A control means monitors the counter value of the counter and when the counter value becomes the value of (m), the output of the subtracting means is outputted as a solution of 2m.M mod N.