Patent ID: 7831651

Claim:
A GCD calculation apparatus for a modular inversion in information security service, where GCD stands for greatest common divisor, comprising: input means for inputting input values X and Y; storage means for storing said input values X and Y, respectively; GCD simulation initializing means for finding values U 0 and V 0 which maximize a value z 0 in an expression gcd(X, Y)=gcd(U 0 , V 0 )2 z0 for said input values X and Y, said gcd(A, B) representing the greatest common divisor for A and B; GCD calculation simulating means for finding values u u , u v , v v and v u which satisfy the following expression, gcd( U 0 ,V 0 )=gcd( |u u U 0 −u v V 0 |/2 w′ ,|v v V 0 −v u U 0 |/2 w′ ) for a predetermined integer w′≧4, from said U 0 and V 0 ; a multi-precision calculating processor for performing the following calculation for said values U 0 , V 0 , u u , u v , v v and v u U′=|u u U 0 −u v V 0 |/2 w′ , V′=|v v V 0 −v u U 0 |/2 w′ and outputting said values U 0 and V 0 ; control means for controlling read and write of said storage means and for repeating operations of said GCD calculation simulating means and said multi-precision calculating processor until V 0 =0 is reached or a bit size of a larger one of the U 0 and V 0 becomes w′ or smaller; GCD calculation final processing means for calculating gcd(U 0 , V 0 )2 z0 for said U 0 and V 0 ; and output means for outputting said calculation result gcd(X, Y) to be used for calculation of an encrypted message, a decrypted message or a digital signature in the information security service.