Patent ID: 7574469
Filing Date: 2009-08-11
Classification: G06F

Abstract:
1. A method for generating the multiplicative inverse in a finite field GF(p), for which it holds that b=q −1 mod p, where (p) is a prime greater than (q) and where (q) is a positive integer greater than one, where, for the number of bits (n) in a register, it holds that 2 where D(x) represents the image of the number x in the two's complement code so that in the first through fifth register (Ru, Rv, Rr Rs a Rm), the least significant bit (LSB) is located on the right, after this initialization is finished, if it is ascertained during the test of the first register (Ru) that the two most significant bits of this first register (Ru) are zero, or are non-zero and at the same time at least one of the remaining bits is not a zero, if it is ascertained that cu≧cv, if cu<cv, the content of the first register (Ru) is shifted by one bit to the left, then, if it is ascertained that the two most significant bits of this second register (Rv) are zero, or are non-zero and at the same time at least one of the remaining bits is not a zero, if it is ascertained that cv≧cu, if it is concluded that both of the most significant bits have the same value and it holds that cv≧cu, if the values of both of the most significant bits of the first and second register (Ru) and (Rv) are equal and it holds that cu>cv, then if it is found that the most significant bit of the first register (Ru) and the most significant bit of the second register (Rv) have different values and at the same time cv≧cu, if cv<cu, then if this is true, if both of these values are non-zero, if the value of the most significant bit of the first register (Ru) is non-zero and the value of the most significant bit of the third register (Rr) is zero, if the value of the most significant bit of the first register (Ru) is zero and the value of the most significant bit of the third register (Rr) is non-zero,