Patent ID: 6237015
Filing Date: 2001-05-22
Classification: G06F

Abstract:
A method for the production, in an integrated circuit, of a parameter J0 associated with the implementation of modular operations according to the Montgomery method, with J0 encoded on Q*L bits such that J0=J0L-1 . . . J00, with Q and L being integers,wherein the method comprises the following steps:Step 1: the loading of a binary data element N0, encoded on Q*L bits, the least significant bit of N0 being equal to 1, in a first register, the loading of Q*L zeros in the second and third register and L zeros in a fourth register;Step 2: the making of a loop of Q iterations comprising the following steps, indexed by j, with j varying from 0 to Q-1:Step 2.1: the making of a loop of L iterations, indexed by i with i varying from 0 to L-1, comprising the following steps:the shifting of the contents of the fourth register by one unit towards the right, this operation corresponding to a division by two of the contents of this register, in overlooking the remainder;the testing of the bit derived from this shift in a test circuit:If the bit checked is at 1: the rightward shifting of the contents of the third register by one unit towards the right and the loading of a zero, on the most significant bit of this register and in a fifth register; the bit-by-bit addition of the contents of the fourth register with a zero in a first adder, an output of this first adder being connected to the input of the fourth register, and the testing of the second least significant bit at output of the first adder;Else: the rightward shifting of the contents of the third register by one unit towards the right; the loading of a 1 on the most significant bit of the third register and in the fifth register; the bit-by-bit addition of the contents of the fourth register and the L last bits of the first register in the first adder, the output of this first adder being connected to the input of the fourth register, the first register forming an L bit register whose input and output are connected, and the testing of the second least significant bit at output of the first adder;Step 2.2: The shifting of the contents of the entire first register and the multiplication, in a multiplication circuit, of the contents of the first register by the contents of the fifth register, said fifth register having been replenished with logic zeros if its size is greater than L; the shifting of the contents of the second register and the addition of these contents with the result of the multiplication, encoded on Q*L+L bits, in a second adder; the storage, in the second register, of the Q*L most significant bits of the binary data element produced by the second adder, and the storage of the L least significant bits of these Q*L bits in the fourth register.