Polynomial inverse computing apparatus, multiplier apparatus and polynomial inverse computing method

A polynomial inverse computing apparatus comprising:

• a first register which stores a divisor as an initial value;
• a second register which stores a modulo as an initial value and holds a content of the first register in a first condition;
• a third register which stores a dividend as an initial value;
• a fourth register which stores a zero value as an initial value and holds a content of the third register in the first condition;
• a fifth register which stores a number of bits of the modulo as an initial value;
• a sixth register which stores the zero value as an initial value;
• a first exclusive-OR unit configured to obtain a first exclusive-OR result of contents of the first register and the second register and outputs the first exclusive-OR result to the first register in the first condition;
• a second exclusive-OR unit configured to obtain a second exclusive-OR result of contents of the third register and the fourth register and outputs the second exclusive-OR result to the third register in the first condition;
• a left shift unit configured to left-shift the content of the first register in a second condition;
• a doubling computing unit configured to execute doubling computation on the content of the third register in an extension field with characteristic 2 in the second condition;
• a first decrement unit configured to decrement a content of the fifth register in the second condition;
• a second decrement unit configured to decrement a content of the sixth register in the second condition;
• a halving computing unit configured to executes halving computation on a content of the fourth register in the extension field with characteristic 2 in a third condition;
• an increment unit configured to increment the content of the sixth register in the third condition;
• a first determination unit configured to determine, in a fourth condition, whether or not the content of the fifth register is the zero value;
• and
• a second determination unit configured to determine, in a fifth condition, whether or not the content of the sixth register is the zero value.

A multiplier apparatus comprising:

• a plurality of registers including a first register, a second register, a third register, and a fourth register,
• the first register, the second register, the third register, and the fourth register store a multiplier, a zero value, a multiplicand, and a modulo, respectively, the registers being used for a polynomial inverse computing apparatus;
• a determination unit configured to determine whether or not a content of the fourth register is the zero value;
• if the determination unit determines the content of the fourth register is a non-zero value,
• a decrement unit configured to decrement the content of the fourth register;
• a doubling computing unit configured to execute doubling computation in an extension field with characteristic 2 to the second register;
• a left shift unit configured to left-shift the content of the first register;
• if a most significant bit of the first register is 1,
• a exclusive-OR unit configured to obtain a exclusive-OR result of contents of the second register and the third register and output the exclusive-OR result to the second register;
• and
• an output unit configured to output a content of the second register if the determination unit determines the content of the fourth register is the zero value.

A polynomial inverse computing method comprising:

• storing, as initial values into a first register, a second register, a third register, a fourth register, a fifth register, and a sixth register, a divisor, a modulo, a dividend, a zero value, a number of bits of the modulo and the zero value, respectively;
• in a first state, unless a most significant bit of the first register is 1, repeatedly performing a first series of operations, the first series of operations including
• left-shifting a content of the first register,
• doubling a content of the third register,
• decrementing a content of the fifth register by 1, and
• incrementing a content of the sixth register by 1,
• the first state being;
• in a second state shifted from the first state if the most significant bit of the first register is 1,
• storing an output of a first exclusive-OR unit which inputs contents of the first register and the second register, and the content of the first register into the first register and the second register, respectively, and
• storing a second exclusive-OR unit which inputs contents of the third register and the fourth register, and the content of the third register into the third register and the fourth register, respectively,
• in a third state shifted from the second state after the second state finishes, unless the content of the sixth register is the zero value, and as long as the most significant bit of the first register is 1, repeatedly performing a second series of operations, the second series of operations including
• storing the output of the first exclusive-OR unit into the first register,
• storing the output of the second exclusive-OR unit into the third register,
• decrementing the content of the sixth register by 1, left-shifting the content of the first register, and
• halving the content of the fourth register,
• the third state being shifted to the first state if the content of the sixth register is the zero value and if the content of the fifth register is non-zero value,
• the content of the fourth register being output as a result if the content of the sixth register is the zero value and if the content of the fifth register is the zero value.