Patent ID: 6978016

Claim:
A method for calculating the multiplicative inverse of an odd binary number, A, modulo R, where R is a positive integer power of two, 2 k , said method comprising the steps of: initializing a first storage element having k bits, for a variable S, to a binary 1; initializing a second storage element having k bits, for a variable Q, with the number A whose multiplicative inverse modulo R is to be determined; for sequential values of i running from 1 to k−1, carrying out the following operations: (a) shifting the contents of the second storage element right by one bit position; (b) determining the current rightmost bit in said second storage element; and (c) upon said rightmost bit position being determined to be a 1, increasing the value stored in said first storage element by 2 i and increasing the value stored in said second storage element by A.