Patent ID: 7068785

Claim:
A method for performing modular division operations used in a cryptographic process over a finite field F U defined for a prime number U to generate a cryptographic key, in which cryptographic process at least one value is divided by an integer divisor V modulo U, the method comprising the steps of calculating an arithmetic inverse of V modulo U using an extended greatest common divisor (GCD) method which includes a plurality of reduction steps and a plurality of inverse calculations, including the steps of: assigning U and V as initial values to respective temporary variables U3 and V3 which are used to calculate the GCD of U and V; assigning initial values to respective temporary variables U2 and V2 which are used to calculate an arithmetic inverse of V module U; determining whether U3 has a number, N, of zero-valued least significant bits (LSBs), where N is an integer greater than two, and if N is greater than two, combining multiple ones of the plurality of reduction steps for calculating the GCD; and combining multiple ones of the plurality of inversion calculations; and if N is not greater than 2, performing a single one of the reduction steps; and performing a single one of the inverse calculation steps; returning, as a result of the plurality of reduction steps and the plurality of inverse calculations, the arithmetic inverse of V; and as a part of the cryptographic process, multiplying the at least one value by the returned arithmetic inverse in place of the integer division to produce the cryptographic key.