condory Just Arrived
Joined: 16 Aug 2009 Posts: 0
|
Posted: Sun Aug 16, 2009 1:33 pm Post subject: Encryption Math - Inverse question. |
|
|
Hello, I would like to know how to calculate the inverse of each element in: Group Z*11?
The elements are: {1,2,3,4,5,6,7,8,9,10}, but how do u get the inverse?
|
|
mah$us Just Arrived
Joined: 25 Feb 2009 Posts: 0
|
Posted: Sun Aug 16, 2009 4:59 pm Post subject: |
|
|
Probably you already know this, but for review:
In a group with operator o, the identity element e is the element with the property a o e = e o a = a. In a group like Z*11, where o is integer multiplication, e = 1.
The inverse of any element a is element b such that a o b = b o a = e.
In a small modular group like Z*11, it is easy to find the inverses by trial an error. For example, to find the inverse of 9:
9 * 2 = 18 = 7 (mod 11)
9 * 3 = 27 = 5 (mod 11)
9 * 4 = 36 = 3 (mod 11)
9 * 5 = 45 = 1 (mod 11) BINGO!
So the inverse of 9 in Z*11 is 5, and automatically we know also the the inverse of 5 is 9.
Obviously, this is infeasible for the enormous finite groups (Z*p where p is hundreds of decimal digits) used in real cryptosystems. It so happens that the sequence of divisions used in Euclid's algorithm to find the greatest common divisor gcd(p, a), where a is an element of Z*p, can be used to compute the inverse. Of course, the primary result of the gcd computation will be 1, because if a were not coprime to the modulus, no inverse would exists. But the steps of division that lead to that remainder of 1 enable computation of the inverse (if an inverse exists, that is, if element a is coprime to the modulus).
In Z*p, because p is prime, EVERY integer from 1 to p-1 is coprime to p, so all of these integers are members of the group, so |Z*p| = p-1. It is quite different for composite moduli - for example, Z*24 = {1, 5, 7, 11, 13, 17, 19, 23}. [This group also has the curious property that every element is its own inverse, so every element of Z*24 is a square root of 1.]
There is more than one way to use Euclid's algorithm to get the inverse. The oldest method uses a kind of back-tracking: starting with the last quotient, you can work backwards through the divisions. Several clever algorithmic variants of Euclid have been devised, which avoid this need for back-tracking. A good survey is at http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm. With a big integer library, you can program an extended euclidean function to compute modular inverses in just a dozen or so lines of code.
|
|