Patent ID: 6914983

Claim:
A method for checksum generation and utilization, in an apparatus for performing modulo N multiplication of integers A and B in which said modulo multiplication is carried out in k bit wide portions of the factors A and B which are representable and as ∑ i = 0 m - 1 ⁢ A i ⁢ R i ⁢ ⁢ and ⁢ ⁢ ∑ i = 0 m - 1 ⁢ B i ⁢ R i where R equals 2 k and where N is representable as ∑ i = 0 m - 1 ⁢ N i ⁢ R i , said method comprising the steps of: operating said multiplication apparatus over a plurality of cycles so as to produce, at each cycle i, the values Z i and Y i in accordance with a two phase modular multiplication method which does not require division operation; accumulating, over said cycles, sums modulo (R−1) of the values A i , B i , N i , Y i and Z i ; and comparing the sum of the Z i values with the sum of two products, the first product being the product of the sums of the A i and B i terms, and the second product being the product of the sums of the N i and Y i terms.