Method for efficient generation of modulo inverse for public key cryptosystems

A method for efficient generation by a computer system of a modulo inverse for a public-key cryptosystem, comprising:

• receiving, in the computer system, first value and a second value for generating one or more public keys for the public-key cryptosystem;
• generating, in the computer system, a modulo inverse for the first value and the second value;
• outputting the modulo inverse to the public-key cryptosystem to generate the one or more public keys;
• and
• performing an encryption function using the one or more public keys,
• wherein generating the modulo inverse comprises:
• storing the first value in a first variable, A, and the second value in a second variable, B;
• determining a remainder, D, of A divided by B;
• responsive to D being greater than one, setting A to be equal to D;
• setting a third variable, U, to be equal to A;
• setting a fourth variable, V, to be equal to B;
• setting a fifth variable, R, to be equal to zero;
• setting a sixth variable, S, to be equal to zero;
• setting a seventh variable, Q, to be equal to one;
• and, setting a modulo inverse variable, G, to be equal to one;
• performing the following until U=O:
• responsive to U being even, repeatedly setting O=Q+B and R=R−A, if R or Q is odd, and shifting U, Q, and R to the right by one bit, until U is odd;
• responsive to V being even, repeatedly setting S=S+B and G=G−A, if S or G is odd, and shifting V, S, and G to the right by one bit until V is odd;
• setting V=V−U and S=S−Q and G=G−R if U is less than V;
• and
• setting U=U−V and Q=Q−S and R=R−G if U is greater than or equal to V;
• responsive to V being equal to one, performing the following:
• responsive to G being less than zero, setting G=A−(|G| MOD A);
• responsive to G being greater than A, setting G=G MOD A;
• determining a quotient, H, and a remainder, N, based on the modulo inverse variable, G;
• and
• determining the modulo inverse based on G, H, and a quotient of A and B.