2. Multiplicative Inverse In GF¶

2.1. Knowledge required¶

Galois Field

2.2. Definition¶

For two integers a and p, the modular multiplicative inverse of a is an integer x such that \(ax \equiv 1 ~mod~p\).

In real number field, if \(ax = 1\). then \(x = 1/a\).

In GF(p), there are only integers. In other word \(x = 1/a\) is also an integer

The method to be introduced here is extended Euclidean algorithm.

2.3. Extended Euclidean algorithm¶

2.3.1. Example 1¶

Find the multiplicative inverse of 1234 in GF(4321).

Q is the quotient of the larger number divided by the smaller number in one row of the first two columns in the table.

The fourth and fifth columns are computed by either copying the previous result or doing subtraction.

4321	1234	Q	(1,0)	(0,1)
4321- 3*1234=619	1234	3	(1,0)-3*(0,1)=(1,-3)	(0,1)
619	1234-1*619=615	1	(1,-3)	(0,1)-1*(1,-3)=(-1,4)
619-1*615=4	615	1	(1,-3)-1*(-1,4)=(2,-7)	(-1,4)
4	615-153*4=3	153	(2,-7)	(-1,4)-153*(2,-7)=(-307,1075)
4-1*3=1	3	1	(2,-7)-(-307,1075)=(309,-1082)	(-307,1075)

When either of the values in the first or second column reaches 1, stop continuing. If the first column reaches 1, find the result in the fourth column, or look into the fifth column.

Then we know that

\[1 = 309 * 4321 - 1082 * 1234.\]

Take the modular operation on both side

\[1~mod~4321 = (309 * 4321 - 1082 * 1234)~mod~4321 = (-1082) * 1234 ~mod~4321.\]

Number -1082 is one candidate inverse of 1234. But an integer in [0, 4321] is preferred. So we do

\[-1082~mod~4321 = 3239\]

Number 3239 is a multiplicative inverse of 1234 in GF(4321). We can check that

\[3239 * 1234 ~mod~4321 = 3996926~mod~4321 = 1.\]

2.4. Add-ups¶

As mentioned in GF, not all the integers have multiplicative inverse. There are some restrictions on the modulo p. If p is a prime number, or exponential of a prime number, the inverse always exists. If a and p are coprime (gcd(a, p) = 1), we can also find an inverse for a. Otherwise, the inverse of a doesn’t exist.

2.4.1. Example 2¶

Find the multiplicative inverse of 24140 in GF(40902).

40902	24140	Q	(1, 0)	(0, 1)
16762	24140	1	(1, -1)	(0, 1)
16762	7378	1	(1, -1)	(-1,2)
2006	7378	2	(3,-5)	(-1,2)
2006	1360	3	(3,-5)	(-10,17)
646	1360	1	(13,-22)	(-10,17)
646	68	2	(13,-22)	(-36,61)
34	68	9	(337,-571)	(-36,61)
34	0	2	(337,-571)	(-710,1203)

We find that one of the column reaches 0. It means :math: ‘gcd(40902, 24140)=34’. 24140 doesn’t have an inverse in GF(40902).