Modulo operation method and apparatus for same

A modulo operation apparatus, in a case where the square of a divisor N is greater than or equal to a dividend C, comprising:

• a plurality of operation blocks connected in series, and
• a control block determining the number of computation stages n satisfying 2n<N≦2n+1, setting a constant a of a 1st operation block to the smallest integer greater than or equal to half of N, setting a constant a of x-th operation block to the smallest integer greater than or equal to half of a of x−1-th operation block, and outputting the value of C output from n-th operation block as the result of a modulo operation,
• wherein each operation block comprises:
• a multiplier taking N and a as input and outputting the value of N·a, wherein N·a is the product of N and a;
• a subtractor taking C output from the x−1-th operation block and the value of N·a output from the multiplier as input, and outputting the value of subtracting the value of N·a from C;
• and
• a first comparator taking C output from the x−1-th operation block and the value of N·a output from the multiplier as input, and outputting output of the subtractor as the value of C for the next operation block, when C is greater than or equal to N·a.

A modulo operation apparatus, in a case where the square of a divisor N is greater than or equal to a dividend C, comprising:

• an operation block;
• and
• a control block determining the number of computation stages n satisfying 2n<N≦2n+1, setting a constant a of a 1st operation block to the smallest integer greater than or equal to half of N, setting a constant a of x-th operation block to the smallest integer greater than or equal to half of a of x−1-th operation block, and outputting the value of C output from n-th operation block as the result of modulo operation,
• wherein the operation block comprises:
• a multiplier taking N and a as input and outputting the value of N·a, wherein N·a is the product of N and a;
• a subtractor taking C output from the x−1-th operation block and the value of N·a output from the multiplier as input, and outputting the value of subtracting the value of N·a from C;
• and
• a first comparator taking C output from the x−1-th operation block and the value of N·a output from the multiplier as input, and outputting the output of the subtractor as the value of C for the next operation block, when C is greater than or equal to N·a.