Modular arithmetic coprocessor comprising two multiplication circuits working in parallel

A method for the implementation of a non-modular multiplication A*B, A and B being pieces of binary data encoded in n bits, n being an integer, these pieces of data being subdivided into m words of k bits A=Am−1 . . . A0 and B=Bm−1 . . . B0, m being an even number, the method comprising the following steps:

• 1—Initialization:
• loading the pieces of data A and B into first and second n-bit registers with series input and output, and loading the words A0 and A1 into third and fourth k-bit registers with series input and parallel output,
• initializing first and second addition circuits and first and second multiplication circuits,
• selecting a first input of a first multiplexer so that it permanently supplies logic zeros to a first series input of the first addition circuit,
• selecting an input of a second multiplexer so that the pieces of data produced by the second multiplication circuit are given with a delay of k clock strokes to a series input of the second addition circuit,
• selecting inputs of a third and fourth multiplexers so as to connect an output of the first register to series inputs of the first and second multiplication circuits;
• 2—Implementation of a computation loop with i as an index varying from 1 to m/2
• 2.1—Iteration 1:
• loading the contents of the third and fourth registers into fifth and sixth k-bit registers with parallel input and output, these outputs being connected to parallel inputs of the first and second multiplication circuits,
• performing, by simultaneous rightward shifting of the contents of the first register and of a seventh n-bit register with series input and output, multiplication operations of the words A1 and A0 by the piece of data B, the pieces of data produced by the first and second multiplication circuits being encoded on n+k bits,
• adding, in the first addition circuit, the bits produced by the first multiplication circuit with the bits given by the first multiplexer,
• storing of the k first bits produced by the first multiplication circuit in an eighth n-bit register with series input and output,
• adding, in the second addition circuit, the n+k bits produced by the second multiplication circuit with the n most significant bits produced by the first multiplication circuit, these bits being complemented by k zeros,
• storaging, in the eighth register, of the k first bits produced by the second addition circuit and the storage, in the seventh register, of the following n bits,
• during the above operations, transferring the words A3 and A2 into the third and fourth registers,
• selecting of a second input of the first multiplexer in order to connect the output of the seventh register to the first input of the first addition circuit;
• 2.j—iteration j, j varying from 2 to m/2−1:
• loading the contents of the third and fourth registers into the fifth and sixth registers,
• performing, by simultaneous rightward shifting of the contents of the first and seventh registers, multiplication operations of the words A2j−1 and A2j−2 by the piece of data B,
• adding, in the first addition circuit, the bits produced by the first multiplication circuit with the contents of the seventh register,
• storing the k first bits produced by the first addition circuit in the eighth register,
• adding, in the second addition circuit, the n+k bits produced by the second multiplication circuit with the n most significant bits produced by the first addition circuit complemented by k zeros to obtain an identical size for the pieces of data that are added up,
• storing, in the eighth register, the k first bits produced by the second addition circuit and the storage, in the seventh register, of the n following bits,
• during the above operations, the transfer of the words A2j+1 and A2j into the third and fourth registers;
• and
• 2.m/2—iteration m/2
• Resuming step 2.j, apart from the transfer of words from the second register into the third and fourth registers, the n least significant bits of the result being in the eighth register and the n most significant bits of the result being in the seventh register at the end of this iteration.