Patent Document ID: 20030147529
Application ID: 10067563
Patent Status: 0

Claim One:
1. A method for performing modular division operations used in a cryptographic process over a finite field F U defined for a prime number U, in which values are 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 modulo U; testing a condition and, if the condition tests true, 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 the condition tests false, performing a single one of the reduction steps; and performing a single one of the inverse calculation steps.