Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
1999-03-31
2002-10-22
Ngo, Chuong Dinh (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C708S491000
Reexamination Certificate
active
06470372
ABSTRACT:
FIELD OF THE INVENTION
The invention relates to the field of microprocesors, and, more particularly, to a modular arithmetic coprocessor that performs an integer division.
BACKGROUND OF THE INVENTION
As described in international Patent Application PCT/FR 97/00035, there already exist known modular arithmetic coprocessors implementing modular exponential operations. This type of operation enables encryption and decryption of binary messages encoded in an RSA type encoding. This type of coprocessor, described, for example, in European Patent Application No. 601,907 can not be used to perform integer divisions. However, the use of an RSA encoding requires the performance of such division operations. It therefore becomes necessary to use a processor to perform these divisions. This involves penalties in terms of computation duration and requires the use of a large-sized program and data memory.
The above referenced international patent application modifies the coprocessor disclosed in the European patent application to perform integer divisions without using a processor. Nonetheless, there is still a need to reduce computation times in performing an integer division.
SUMMARY OF THE INVENTION
A method for performing an integer division in a coprocessor divides a first data element M by a second data element D. The first data element M is binary encoded on m words M(m−1) . . . M(
1
), M(
0
) of L bits. The second data element D is binary encoded on d words D(d−1) . . . D(
1
), D(
0
) of L bits. The variables m, L and d are integers and d<m. The result referenced as Q is encoded on q words Q(q−1), Q(q−2) . . . Q(
1
), Q(
0
) of L bits with q=m−d+1 and Q(q−1)=00 . . . 00 or 00 . . . 01.
The method includes the steps of taking the complement of the data element M by a most significant word bit M(m) formed by L zeros, and performing a computational iterative loop m−d+1 times. The computational iterative loop includes the steps of producing a first intermediate data element Q(q−1−j), with j as an index varying from 0 to q−1 and binary encoded on L bits for performing an integer division of the two most significant words of the first data element M by the most significant word of the second data element D a second intermediate data element Z(m−j)binary encoded on 2 *L bits is produced to test and determine whether the first intermediate data element Q(q−1−j) is greater than a desired value of one of the words of the result Q, or whether it corresponds to a desired value of one of the following words.
In the former case, the first intermediate data element is decremented by one unit and the previous step is repeated. In the second case, the multiplication of the second data element D by the first intermediate data element Q(q−1−j) is performed to form a third intermediate data element B binary encoded on d+1 words of L bits. The d new most significant words M(m−j−1) . . . M(m−j−d) of the first data element are generated for performing a subtraction of the third intermediate data element B from the d+1 non-zero most significant bits of the first data element, except during the first iteration where the word M(m) and the d most significant words of the first data element M are considered. If the result of the subtraction is negative, the first intermediate data element is decremented by one unit and the d new most significant words are modified by adding the second data element to these words.
According to one embodiment, the method preferably includes the following steps E
1
-E
6
. Step E
1
includes the steps of loading the word M(m−1) into a first register; the most significant bit of this word being provided as an output of the first register; loading of L zeros corresponding to a word M(m) in a second register; loading L zeros into a third register; loading the word D(d−1) into a fourth register; and the least significant bit of this word is provided at an output of the fourth register.
The repetition q times of the following steps E
2
-E
6
are performed, where j is an index varying from 0 to q−1. Step E
2
is the integer division of the contents of the second and first registers by the contents of the fourth register; and the storage of the L least significant bits of the result, referenced Q(q−1−j), in the first register and in the fifth and sixth registers.
Step E
3
includes the steps of loading the word D(d−2) into the second register; the least significant bit of this word is provided at an output of the second register; loading the words M(m−1−j) and M(m−j) in series in the third register; the least significant bits being directed towards the output of this third register; loading of the word M(m−2−j) into a seventh register, and the least significant bit of this word being directed towards the output of the seventh register.
Step E
4
includes the steps of shifting the contents of the second and fourth registers towards series inputs of a first multiplication circuit and a second multiplication circuit, and the contents of the third and seventh registers, with looping of the outputs of these registers to their inputs; multiplying D(d−2) by Q(q−1−j) in the first multiplication circuit; multiplying D(d−1) by Q(q−1−j) in the second multiplication circuit; subtracting M(m−j)M(m−j−1) from D(d−1)*Q(q−1−j) in a first subtraction circuit; subtracting M(m−2−j) from the data element produced by the first subtraction circuit in a second subtraction circuit; the word M(m−2−j) is delayed in a delay cell; subtracting the data element produced by the second subtraction circuit from D(d−2)*Q(q−1−j) in a third subtraction circuit; and testing the result of the last subtraction in a test circuit.
Step E
5
includes the steps of determining that if the result of the last subtraction of the step E
4
is positive, then the contents of the first register are shifted; subtracting an L bit data element formed by a least significant bit at one and of L−1 most significant bit at zero from the data element Q(q−1−j) initially present in the first register; subtracting being done in a fourth subtraction circuit, and storing the data element produced by the fourth subtraction circuit in the first register; and step E
4
is repeated.
Step E
6
includes the steps of determining the result of the last subtraction of step E
4
is negative, then the words M(m−j) . . . M(m−d−j) are loaded in the third register and the data element D is loaded in the fourth register; shifting the contents of the third and fourth registers with the looping of the output of the fourth register to its input so as to keep D(d−1) in this register; multiplying the data element D by the data element Q(q−1−j) in the second multiplication circuit; subtracting the result produced by the second multiplication circuit from the bits given by the third register in the first subtraction circuit, and the testing of the result.
Step E
6
further includes the steps of determining that if the result given by the first subtraction circuit is negative, then the data element D given by the fourth register is added to the result produced by the first subtraction circuit in an addition circuit; subtracting an L bit data element formed by a least significant bit at one and by L−1 most significant bits at zero from the data element Q(q−1−j) initially present in the first register, the subtraction being done in the fourth subtraction circuit; and storing the data element produced by the fourth subtraction circuit in the first register; storing the last two words of the result produced by the first subtraction circuit or, as the case may be, by the addition circuit, referenced M(m−1−j) . . . M(m−d−j), in the second and first registers, t
Allen Dyer Doppelt Milbrath & Gilchrist, P.A.
Jorgenson Lisa K.
Ngo Chuong Dinh
STMicroelectronics S.A.
LandOfFree
Method for the performance of an integer division does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for the performance of an integer division, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for the performance of an integer division will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2934168