Computer Communications 31 (2008) 4117–4123

Contents lists available at ScienceDirect

Computer Communications
journal homepage: www.elsevier.com/locate/comcom

Methods of finding multiplicative inverses in GF(28)

Manzar Saeed *, M. Saleem Mian 1
Department of Electrical Engineering, University of Engineering and Technology, Lahore 54890, Pakistan

a r t i c l e i n f o a b s t r a c t

Article history: Finding the multiplicative inverse of an element in Galois Field(p), GF(p) for small values of p such as 5 or
Received 13 January 2008 7 is no problem. One can find the multiplicative inverse by constructing multiplication tables and estab-
Accepted 22 August 2008 lish the desired value directly. The look-up table procedure, when implemented through software, is fast
Available online 2 September 2008
and handy, and is employed in the design of S-boxes of the Rijndael encryption algorithm used in
advanced encryption standard (AES). However, a second choice, if execution time is not the consideration,
Keywords: is the use of extended Euclid’s algorithm. The two methods of finding multiplicative inverse in GF(28) pre-
gcd
sented in many books are discussed in this paper. An effort is made to present the working of these meth-
Multiplicative inverse
Finite fields
ods in a detailed manner which is not found in any text. A comparison of these methods vis-à-vis time,
Euclid’s algorithm transistor count and complexity is also made. Section 1 contains a brief introduction to the topic, Section
{xx} hexadecimal  xx16 2 reviews multiplication in polynomial arithmetic. Multiplicative inverses in GF(28) are taken up in Sec-
tions 3, and 4 concludes the paper.
Ó 2008 Elsevier B.V. All rights reserved.

1. Introduction fields) used in AES, will be considered. The technique rests on

the following observation:
Two numbers are co prime when they share no factors in com-
x8 modaðxÞ ¼ ðaðxÞ  x8 Þ ¼ x4 þ x3 þ x þ 1 ð1:1Þ
mon other than 1. In other words, if greatest common divisor (gcd)
8
of a and b is equal to 1, they are co prime. This is written as A polynomial in GF(2 ) can have the following form:
gcdða; bÞ ¼ 1 f ðxÞ ¼ b7 x7 þ b6 x6 þ b5 x5 þ b4 x4 þ b3 x3 þ b2 x2 þ b1 x þ b0 ð1:2Þ
The numbers 15 and 28 are co prime, 15 and 27 are not, 13 and 500 Multiplying Eq. 1.2 by x on both sides will produce
are and so on [1].
Generally, if gcd( a, b) = 1, then b has a multiplicative inverse xf ðxÞ ¼ ðb7 x8 þ b6 x7 þ b5 x6 þ b4 x5 þ b3 x4 þ b2 x3 þ b1 x2
modulo a. In other words, for positive integer b < a, there exists a þ b0 xÞ mod aðxÞ ð1:3Þ
b^{1} < a such that b  b^{1} = 1 mod a [11]. The extended Eu-
clid’s algorithm is a wonderful procedure to find gcd(a, b) and for The subsequent observations are helpful to understand the material
a special case if gcd( a, b) = 1, the algorithm returns the value of to follow:
the multiplicative inverse of b. This, however, will be taken up later
in this paper. First, a procedure using look-up tables will be illus- 1. For a special case of b7 = 0, the order of the polynomial will be
trated to find the multiplicative inverse in GF(28). less than 8; and in such a case no more operations are needed
as the polynomial is already in the reduced form.
2. However, if b7 = 1, then reduction modulo a(x) has to be per-
2. Multiplication in polynomial arithmetic
formed as given in 1.1.
Multiplication of two fields in GF(28) is based on the following
The meaning of Cases (1) and (2) is summarized in 1.4.
observation given in Eq. 1.1. In the discussion to follow,

a(x) = x8 + x4 + x3 + x + 1 = {l1B} in hexadecimal notation, (an eighth ðb6 b5 b4 b3 b2 b1 b0 0Þ if b7 ¼ 0
degree irreducible polynomial [2,9,11] and is one of the finite xf ðxÞ ¼ ð1:4Þ
ðb6 b5 b4 b3 b2 b1 b0 0Þ  00011011 if b7 ¼ 1

As given in [11], Eq. 1.4 is the foundation for multiplication in

GF(28). The meaning of above equation is that multiplication by
* Corresponding author. Tel.: +92 042 521 0707.
E-mail addresses: manzarsaeed@yahoo.com (M. Saeed), drmsaleem@gmail.com
x = 0000 0010 can be achieved as a 1-bit left-shift operation fol-
(M. Saleem Mian). lowed by a conditional bitwise exclusive-OR (XOR) with 0001
1
Tel.: +92 042 902 9229. 1011 (which is another way of expressing x4 + x3 + x + 1).

0140-3664/$ - see front matter Ó 2008 Elsevier B.V. All rights reserved.
doi:10.1016/j.comcom.2008.08.018
4118 M. Saeed, M. Saleem Mian / Computer Communications 31 (2008) 4117–4123

Generally, any multiplication by a higher power of x can be had These calculations reveal that successive powers of 5 just take on
by repeatedly using Eq. 1.4 as explained in Section 2.1. the values 5, 12, 8, 1, 5, and repeat after four calculations, hence 5
is not the correct generator for the field under consideration. Simi-
2.1. A brief visit to the finite fields larly, if we try powers of 4, taken modulo 13, the sequence will be:
4, 3, 12, 9, 10, 1, and will repeat, forcing us to conclude once again
Before delving into detailed calculations, a brief introduction to that 4 is certainly not a generator for this field either. However, if
some relevant topics seems appropriate. A field is an algebraic ob- we try successive powers of 2, taken modulo 13, the sequence will
ject with two operations; addition and multiplication, denoted be of maximal length (producing an array of twelve unique num-
respectively by + and *. Using addition (+), all the elements of bers) and then it will repeat. This easily leads us to the conclusion
the field must form a commutative group, with identity indicated that 2 is the true generator for this field. The sequence generated
by 0 and the inverse of a denoted by a. Using multiplication for this field is: 2, 4, 8, 3, 6, 12, 11, 9, 5, 10, 7, 1, and then it will re-
(*), all the elements of the field with the exception of 0 must form peat. The above procedure reveals that generators in a field are dif-
another commutative group [2,8,11] with identity element indi- ficult to find and a lot of calculations must be performed to arrive at
cated by 1 and inverse of a denoted by a^{1}. Also, under * no in- the correct conclusion. It turns out that {03}, which is equivalent to
verse exists for element 0. x + 1 as a polynomial, is the simplest generator for GF(28) field, our
Although, there are plenty of various infinite fields, but cryptog- main concern here. It is, therefore, concluded that its powers will
raphy mainly spotlights on finite fields; particularly AES utilizes take on all 255 non-zero values in this field, as shown in Table 1.1.
GF(28) field extensively. To perform multiplication operation on In order to facilitate this idea a few entries of this table can be
two given polynomials verified as demonstrated below
f ðxÞ ¼ x4 þ x2 þ x þ 1
ðx þ 1Þ00 ¼ 01 ) ðrow 0; column 0Þ
gðxÞ ¼ x5 þ x3 þ x
ðx þ 1Þ01 ¼ x þ 1 ¼ 0:x7 þ 0:x6 þ 0:x5 þ 0:x4 þ 0:x3 þ 0:x2 þ 1:x þ 1
in the finite field (mod (x8 + x4 + x3 + x + 1)) used by AES, one has to
¼ 00000011  0316
express these polynomials in binary notation as
4 2 ) ðrow 0; column 1Þ
f ðxÞ ¼ x þ x þ x þ 1  1716  ð00010111Þ2
02
ðx þ 1Þ ¼ ðx þ 1Þðx þ 1Þ
gðxÞ ¼ x5 þ x3 þ x  2A16  ð00101010Þ2
¼ x2  1:x  1:x  1:1 ¼ x2 þ 1
For the following procedure the subscript of 2 is omitted for binary
notation ¼ 0:x7 þ 0:x6 þ 0:x5 þ 0:x4 þ 0:x3 þ 1:x2 þ 0:x þ 1
 
ð00000010Þ þ ð00001000Þþ ¼ 000001010  0516
ð00010111Þ  ð00101010Þ ¼ ð00010111Þ  ðiÞ
ð00100000Þ ) ðrow 0; column 2Þ
Keeping in view Eq. 1.4, the solution of (i) will yield the following ðx þ 1Þ03 ¼ ðx þ 1Þ02 ðx þ 1Þ
final result: ¼ ðx2 þ 1Þðx þ 1Þ
9
00101110 >
=
10111000  Using above result
>
;
11010110 ðx þ 1Þ03 ¼ x3 þ x2 þ x þ 1
01000000  4016 ¼ 0:x7 þ 0:x6 þ 0:x5 þ 0:x4 þ 1:x3 þ 1:x2 þ 1:x þ 1
The final outcome indicates: 1716 * 2A16 = 4016 in GF(28). ¼ 00001111  0F 16 ) ðrow 0; column 3Þ
Once this basic philosophy is clear, above calculations shall be
cross-checked using look-up table procedure and then the ex- The construction of the inverse of Table 1.1 is a simple and straight-
tended Euclid’s algorithm in Sections 2.2 and 3.2. forward matter as outlined below

2.2. Field generators  This new Table 1.2 is called a table of ‘‘logarithms”.
 The entry L(rs) is called the field element that satisfies the rela-
Field generators are very important and form the foundation for tionship: rs = 03L(rs), where all numbers are, obviously,
producing pseudo random numbers (PRNs) of maximal length, and expressed in hexadecimal.
their importance in numerous cryptographic techniques need not  To construct this table, pick an entry from Table 1.1 and split it
be over-emphasized. The concept of a field generator is incredibly in two parts; the first part becomes the row number, and the
simple; the sequence of numbers generated by taking successive second part becomes the column number for Table 1.2.
powers of an element in a field should produce a sequence that  In fact, the row entry of Table 1.1 becomes the first digit and the
necessarily repeats only after the entire set of numbers (except column number becomes the second digit of Table 1.2.
zero) has been exhausted [8]. If we try in a row powers of several  As an example in Table 1.1 notice entry in row 1, column 7 is ‘A4’
elements in the field Z13 to find a generator, we will end up with  So, we write ‘‘17” in row A, column 4 of Table 1.2.
the conclusion that 2 is the correct generator for this field. For  This way Table 1.2 is constructed.
example, if we try successive powers of 5, taken modulo 13, we
will end with the conclusion that the generated sequence will re- To illustrate the use and importance of the above tables, one can
peat after four iterations and thus will not of maximal length. take the previous multiplication example to find the product of
The following calculations will help to understand this point: two hexadecimal numbers

51 ¼5 1716  2A16
52 % 13 ¼ 12
The values of 1716 and 2A16 are first read from look-up Table 1.2 as
53 % 13 ¼ ð12  5Þ%13 ¼ 8
54 % 13 ¼ ð8  5Þ%13 ¼ 1 Lð17Þ  fEFg and Lð2AÞ  fA6g
55 % 13 ¼ ð1  5Þ%13 ¼ 5 and it starts to repeat then their product will be as given under
 M. Saeed, M. Saleem Mian / Computer Communications 31 (2008) 4117–4123 4119

Table 1.1
Exponentials E(rs) = 03rs

s?
E(rs) 0 1 2 3 4 5 6 7 8 9 A B C D E F
E(rs) = 03rs
0 01 03 05 0F 11 33 55 FF 1A 2E 72 96 Al F8 13 35
"
r 1 5F El 38 48 D8 73 95 A4 F7 02 06 0A IE 22 66 AA
#
2 E5 34 5C E4 37 59 EB 26 6A BE D9 70 90 AB E6 31
3 53 F5 04 0C 14 3C 44 CC 4F Dl 68 B8 D3 6E B2 CD
4 4C D4 67 A9 E0 3B 4D D7 62 A6 Fl 08 18 28 78 88
5 83 9E B9 D0 6B BD DC 7F 81 98 B3 CE 49 DB 76 9A
6 B5 C4 57 F9 10 30 50 F0 0B ID 27 69 BB D6 61 A3
7 FE 19 2B 7D 87 92 AD EC 2F 71 93 AE E9 20 60 A0
8 FB 16 3A 4E D2 6D B7 C2 5D E7 32 56 FA 15 3F 41
9 C3 5E E2 3D 47 C9 40 C0 5B ED 2C 74 9C BF DA 75
A 9F BA D5 64 AC EF 2A 7E 82 9D BC DF 7A 8E 89 80
B 9B B6 Cl 58 E8 23 65 AF EA 25 6F Bl C8 43 C5 54
C FC IF 21 63 A5 F4 07 09 IB 2D 77 99 B0 CB 46 CA
D 45 CF 4A DE 79 8B 86 91 A8 E3 3E 42 C6 51 F3 0E
E 12 36 5A EE 29 7B 8D 8C 8F 8A 85 94 A7 F2 0D 17
F 39 4B DD 7C 84 97 A2 FD 1C 24 6C B4 C7 52 F6 01

(E(rs) is the field element given by 03rs, and the numbers are expressed in hexadecimal [8].)

Table 1.2
Logarithms of L(rs) in the field element that satisfies rs = 03L(rs)

s?
L(rs) 0 1 2 3 4 5 6 7 8 9 A B C D E F
L(rs)
rs = 03
"
r 0 00 19 01 32 02 1A C6 4B C7 IB 68 33 EE DF 03
#
1 64 04 E0 0E 34 8D 81 EF 4C 71 08 C8 F8 69 1C Cl
2 7D E2 ID B5 F9 B9 27 6A 4D E4 A6 72 9A C9 09 78
3 65 2F 8A 05 21 0F El 24 12 F0 82 45 35 93 DA 8E
4 96 8F DB BD 36 D0 CE 94 13 5C D2 Fl 40 46 83 38
5 66 DD FD 30 BF 06 8B 62 B3 25 E2 98 22 88 91 10
6 7E 6E 48 C3 A3 B6 IE 42 3A 6B 28 54 FA 85 3D BA
7 2B 79 0A 15 9B 9F 5E CA 4E D4 AC E5 F3 73 A7 57
8 AF 58 A8 50 F4 EA D6 74 4F AE E9 D5 E7 E6 AD E8
9 2C D7 75 7A EB 16 0B F5 59 CB 5F B0 9C A9 51 A0
A 7F 0C F6 6F 17 C4 49 EC D8 43 IF 2D A4 76 7B B7
B CC BB 3E 5A FB 60 Bl 86 3B 52 Al 6C AA 55 29 9D
C 97 B2 87 90 61 BE DC FC BC 95 CF CD 37 3F 5B D1
D 53 39 84 3C 41 A2 6D 47 14 2A 9E 5D 56 F2 D3 AB
E 44 11 92 D9 23 20 2E 89 B4 7C B8 26 77 99 E3 A5
F 67 4A ED DE C5 31 FE 18 0D 63 8C 80 C0 F7 70 07

(All numbers are expressed in hexadecimal [8].)

1716  2A16 ¼ f03gEF  f03gA6 ¼ f03gEFþA6 ¼ f03g96 The modular inverse problem is much more difficult to solve. It does
96
not have solution in all the cases. For example, the inverse of 5,
Now, Table 1.1 is used to look-up (03) , which gives the answer modulo 14 is 3, and on the other hand, 2 has no inverse modulo
4016 (the same answer as was obtained in Section 2.1). One can 14. Similarly, 3 has a multiplicative inverse modulo 26 because 3
appreciate the ease and efficiency of this look-up table method and 26 have no common prime factors. This multiplicative inverse
compared to the procedure followed above in Section 2.1. These ta- can be obtained by finding number x in Z26 that satisfies the mod-
bles provide us with a much faster method for multiplication. ular equation:

3. Multiplicative inverse in GF(28)

3x ¼ 1 mod ð26Þ
The multiplicative inverse of 4 is 1/4, because 4 * (1/4) = 1. In 3:9 ¼ 27 ¼ 1 mod ð26Þ
modulo arithmetic, the problem is more complicated 31 ¼ 9 mod ð26Þ
4  x  1 mod ð7Þ
Thus, 9 is the multiplicative inverse of 3 modulo 26. Also note that 4
This equation is equivalent to finding x and k such that
has no multiplicative inverse modulo 26 because 4 and 26 have 2 as
4  x ¼ 7k þ 1 a common prime factor [3,4].
where both x and k are integers. In general, a^{1} = x(mod b) has a unique solution if a and b are
The general problem is finding an x such that co prime. If a and b are not co prime, then a^{1} = x (mod b) has
no solution. If b is a prime number, then every number from 1 to
1 ¼ ða  xÞ ¼ mod ðbÞ b  1 is relatively prime to b and has exactly one inverse modulo
This can also be put as b in that range [1].
The following steps will help to find multiplicative inverse in
a1  x mod ðbÞ GF(28).
4120 M. Saeed, M. Saleem Mian / Computer Communications 31 (2008) 4117–4123

1. If g is the generator {03}, then the inverse of grs is gFFrs. Continuing in this manner, one can get the following sequence of
2. To find the multiplicative inverse of {17}, Table 1.2 shows remainders:
{17} = gEF, so the inverse of {17} will be gFFEF=g10.
b ¼ r0 > r1 > r2 > r3 >    P 0
3. Now, the entry {10} from the exponential Table 1.1 (row 1,
column 0) gives the answer {5F}. Since the remainders are non-negative and getting smaller and
4. Therefore, {17}1 = {5F} is the required multiplicative smaller, this sequence should eventually terminate with remainder
inverse of {17} in GF(28). rn = 0. Thus, the last two equations in the above sequence will be
5. Table 1.3 can easily be constructed to get multiplicative
r n2 ¼ qn1 r n1 þ rn for rn 6 r n1
inverse of any number in GF(28), except 0, which has no
inverse. r n1 ¼ qn r n
6. Table 1.3 is very handy for working with AES and allied It follows by induction that
algorithms.
7. Using Tables 1.1–1.3 the multiplicative inverse of the gcdða; bÞ ¼ gcdða; r 0 Þ ¼ gcdðr 0 ; r 1 Þ
polynomial .. ð1:5Þ
.
(x7 + x + 1) mod (x8 + x4 + x3 + x + 1) is found below:
(a) Express the polynomial (x7 + x + 1) in hexadecimal notation ¼ gcdðr n1 ; r n Þ ¼ r n
as {83}. rn is the last non-zero remainder in the sequence, and hence it fol-
(b) Use Table 1.2 and 1.1, then{83}  g50 and {83}1 = gFF-50 = lows [10]:
gAF = {80}is the required answer in hexadecimal and can be
confirmed from Table 1.3, where it is shown in bold. gcdða; bÞ ¼ r n
The sequence q0, q1, . . . , qn1 is called the sequence of partial quo-
tients, and the sequence r2, r3, . . . , rn is called the sequence of
3.1. Euclid’s algorithm remainders [5,6].
Detailed application of this algorithm to find gcd(4617, l175)
The prime factorizations of very large numbers are normally not will be demonstrated now [10].
known. In fact, an important area of research in number theory is
the search for quicker methods of factoring large integers. Fortu- 4617 ¼ 3ð1175Þ þ 1092 ) gcdð1175; 1092Þ
nately, Euclid’s or Euclidean algorithm [7] is a relatively quick 1175 ¼ 1ð1092Þ þ 83 ) gcdð1092; 83Þ
way to find gcd(a, b) of two numbers a or b. 1092 ¼ 13ð83Þ þ 13 ) gcdð83; 13Þ
Generally, Euclid’s algorithm can be employed to find gcd of 83 ¼ 6ð13Þ þ 5 ) gcdð13; 5Þ
two positive integers (or two polynomials), and the extended Eu-
13 ¼ 2ð5Þ þ 3 ) gcdð5; 3Þ
clid’s algorithm (see Section 3.2) can be adapted to find multiplica-
tive inverse of a polynomial. The following algorithm shows the 5 ¼ 1ð3Þ þ 2 ) gcdð3; 2Þ
complete procedure. 3 ¼ 1ð2Þ þ 1 ) gcdð2; 1Þ
Euclid’s algorithm makes repeated use of the equation: 2 ¼ 2ð1Þ þ 0
a = q0b0 + r0 to determine gcd with the essential assumption that
a > b > 0. (the execution stops when a remainder of 0 is obtained). The last
Let a and b be any two positive integers with a P b. If a = b, then non-zero remainder (1) is the required gcd of given numbers, that
gcd(a, b) = a, so let us assume a > b. Then by successive application is, gcd(4617, 1175) = 1. Hence, a = 4617, and b = 1175 are relatively
of the division algorithm, we can get the following sequence of prime. The Euclid algorithm is purely mechanical. The divisor be-
equations [2]: comes the new dividend and the remainder the new divisor [10].
It proceeds in a natural way to produce gcd of two given numbers
a ¼ q0 b0 þ r0 for 0 6 r 0 < b0
and produces the desired result.
b0 ¼ q1 b1 þ r1 for 0 6 r 1 < b1 Based on above observations, the complete Euclid algorithm fol-
b1 ¼ q2 b2 þ r2 for 0 6 r 2 < b2 lows the following equation:

Table 1.3
Multiplicative inverses [8] in GF(28)

s?
rs1 0 1 2 3 4 5 6 7 8 9 A B C D E F
rs * rs1 = 01
"
r 0 Xx 01 8D F6 CB 52 7B Dl E8 4F 29 CO BO E1 E5 C7
#
1 74 B4 AA 4B 99 2B 60 5F 58 3F FD CC FF 40 EE B2
2 3A 6E 5A Fl 55 4D A8 C9 Cl OA 98 15 30 44 A2 C2
3 2C 45 92 6C F3 39 66 42 F2 35 20 6F 77 BB 59 19
4 ID FE 37 67 2D 31 F5 69 A7 64 AB 13 54 25 E9 09
5 ED 5C 05 CA 4C 24 87 BF 18 3E 22 FO 51 EC 61 17
6 16 5E AF D3 49 A6 36 43 F4 47 91 DF 33 93 21 3B
7 79 B7 97 85 10 B5 BA 3C B6 70 DO 06 Al FA 81 82
8 83 7E 7F 80 96 73 BE 56 9B 9E 95 D9 F7 02 B9 A4
9 DE 6A 32 6D D8 8A 84 72 2A 14 9F 88 F9 DC 89 9A
A FB 7C 2E C3 8F B8 65 48 26 C8 12 4A CE E7 D2 62
B OC EO IF EF 11 75 78 71 A5 8E 76 3D BD BC 86 57
C OB 28 2F A3 DA D4 E4 OF A9 27 53 04 IB FC AC E6
D 7A 07 AE 63 C5 DB E2 EA 94 8B C4 D5 9D F8 90 6B
E Bl OD D6 EB C6 OE CF AD 08 4E D7 E3 5D 50 IE B3
F 5B 23 38 34 68 46 03 8C DD 9C 7D AO CD 1A 41 1C
 M. Saeed, M. Saleem Mian / Computer Communications 31 (2008) 4117–4123 4121

gcdða; bÞ ¼ gcdðb; a mod bÞ ð1:6Þ 4. a 83

5. b 13
Another way of treating the above procedure will be now demon-
6. Goto 2 (Iteration 4)
strated with the help of the same example.
gcdð4617; 1175Þ
¼ gcdð1175; 4617 mod 1175Þ Iteration 4:
¼ gcdð1175; 1092Þ 1,2. Not applicable
3. r = a mod b
¼ gcdð1092; 1175 mod 1092Þ
83 mod 13
¼ gcdð1092; 83Þ 5
¼ gcdð83; 1092 mod 83Þ 4. a 13
¼ gcdð83; 13Þ 5. b 5
¼ gcdð13; 83 mod 13Þ 6. Goto 2 (Iteration 5)
¼ gcdð13; 5Þ
¼ gcdð5; 13 mod 5Þ
Iteration 5:
¼ gcdð5; 3Þ 1, 2. Not applicable
¼ gcdð3; 5 mod 3Þ 3. r = a mod b
¼ gcdð3; 2Þ 13 mod 5
¼ gcdð2; 3 mod 2Þ 3
4. a 5
¼ gcdð2; 1Þ
5. b 3
Again, the same result is obtained. The Euclid’s algorithm can now 6. Goto 2 (Iteration 6)
be formally put as follows:

Euclid(a, b) Iteration 6:
1. Initialize a and b 1, 2. Not applicable
2. if b = 0 return a = gcd(a, b) 3. r = a mod b
3. r = a mod b 5 mod 3
4. a b 2
5. b r 4. a 3
6. Goto 2. 5. b 2
6. Goto 2 (Iteration 7)
A step-by-step application of the algorithm will be explained by
taking up the same example with the same given numbers
a ¼4617
Iteration 7:
b ¼1175 1, 2. Not applicable
3. r = a mod b
Iteration 1: 3 mod 2
1. Initialize a and b 1
a 4617, b 1175 5. b 1
2. Not applicable 6. Goto 2 (Iteration 8)
3.r = a mod b
4617 mod 1175
1092 Iteration 8:
4. a 1175 1, 2. Not applicable
5. b 1092 3. r = a mod b
6. Goto 2 (Iteration 2) 2 mod 1
0
4. a 1
Iteration 2: 5. b 0
1, 2. Not applicable 6. Goto 2 (accomplished)
3. r = a mod b
1175 mod 1092 The remainder 0 in Step 5 above indicates that the two num-
83 bers, 4617 and 1175 have a gcd = 1, hence these numbers are rel-
4. a 1092 atively prime.
5. b 83
6. Goto 2 (Iteration 3) 3.2. Extended euclid’s algorithm

Sometimes a little variation of this algorithm, called extended Eu-

Iteration 3: clid’s algorithm can be used to find multiplicative inverse of a prime
1, 2. Not applicable number [1]. Keeping in view the abundant use and importance of
3. r = a mod b finding and using multiplicative inverses in GF(28), the extended Eu-
1092 mod 83 clid’s algorithm can be adopted to determine the multiplicative in-
13 verse of a polynomial. Specially, the algorithm can determine the
4122 M. Saeed, M. Saleem Mian / Computer Communications 31 (2008) 4117–4123

multiplicative inverse of b(x) modulo a(x) if the degree of b(x]is less 5. t1(x) a1(x)  q(x)*b1(x)
than the degree of a(x)and gcd[a(x), b(x)] = 1. The algorithm given 0  (x + 1).1 = (x + 1)
below is based on the basic equation: a = qb + r [11]. t2(x) a2(x)  q(x) * b2(x)
1  (x + 1)(x4 + x2 + x + 1)
Extended Euclid[(a(x), b(x)] (x5 + x4 + x3)
t3(x) a3(x)  q(x) * b3(x)
1. {a1(x),a2(x),a3(x)} {1,0,a(x)} ((x4 + x2 + x + 1)  (x + 1)(x3 + x2 + x))
[{b1(x),b2(x),b3(x)} {1, 0, b(x)}] (x2 + 1)
2. If b3(x) = 0, return a3(x) = gcd[a(x), b(x)]; no inverse 6. [{a1(x), a2(x), a3(x)} {b1(x), b2(x), b3(x)}]
3. If b3(x) = 1, return b3(x) = gcd[a(x), b(x)]; b2(x) = b(x)1 mod a(x) a1(x) 1,
4. q(x) = quotient ofa3(x)/b3(x) a2(x) (x4 + x3 + x + 1),
5. t1(x) a1(x)  q(x)b1(x) a3(x) (x3 + x2 + x).
t2(x) a2(x)  q(x)b2(x) 7. [{b1(x), b2(x), b3(x)} {t1(x), t2(x), t3(x)}]
t3(x) a3(x)  q(x)b3(x) b1(x) (x + 1),
[{b1(x), b2(x), b3(x)} {1,0,b(x)}] b2(x) (x5 + x4 + x3),
6. [a1(x), a2(x), a3(x)] [b1(x), b2(x), b3(x)] b3(x) (x2 + 1).
7. [b1(x), b2(x), b3(x)] [t1(x), t2(x), t3(x)] Goto 2 (accomplished, so iteration 3)
8. Goto 2.

The multiplicative inverse of (x4 + x2 + x + 1) mod Iteration 3:

8 4 3
(x + x + x + x + 1) can be determined again with the help of ex- 2,3 Not applicable
tended Euclid’s algorithm. To facilitate the application of the above 4. q(x) = quotient of a3(x)/b3(x)
3 2 þx
algorithm, one can write as ¼ x xþx
2 þ1 ¼xþ1
5. t1(x) a1(x)  q(x)*b1(x)
bðxÞ ¼ ðx4 þ x2 þ x þ 1Þ ¼ 1716 and
1  (x + 1).(x + 1) = x2
aðxÞ ¼ ðx8 þ x4 þ x3 þ x þ 1Þ ¼ 11B16 t2(x) a2(x)  q(x)*b2(x)
(x4 + x3 + x + 1)  (x + 1)(x5 + x4 + x3)
(x4 + x3 + x2 + x + 1)
Initialization:
t3(x) a3(x)  q(x) * b3(x)
1. {a1(x), a2(x), a3(x)} {1, 0, a(x)}
1
{b1(x), b2(x), b3(x)} {1, 0, b(x)}
6. [{a1(x), a2(x), a3(x)} {b1(x), b2(x), b3(x)}]
a1(x) = 1;a2(x) = 0;a3(x) = a(x)
a1(x) (x + 1),
a3(x) = x8 + x4 + x3 + x + 1;
a2(x) (x5 + x4 + x3),
b1(x) = 0;b2(x) = 1;b3(x) = b(x);
a3(x) (x2 + 1).
b3(x) = (x4 + x2 + x + 1).
7. [{b1(x), b2(x), b3(x)} {t1(x), t2(x), t3(x)}]
b1(x) (x3),
b2(x) (x6 + x4 + x3 + x2 + x + 1),
Iteration 1: b3(x) (1).
2, 3. Not applicable Goto 2 (accomplished, so iteration 4)
4. q(x) = quotient of a3(x)/b3(x)
8 4 þx3 þxþ1
¼ x xþx
4 þx2 þxþ1
4 2
=x + x + x + 1
5. t1(x) a1(x)  q(x)*b1(x)
Iteration 4:
1  (x4 + x2 + x + 1).0 = 1
2,3 Not applicable
t2(x) a2(x)  q(x)*b2(x)
b3(x) = gcd[(x8 + x4 + x3 + x + 1),(x7 + x + 1)] = 1
0  (x4 + x2 + x + 1).1
b2(x) = b1 mod a(x)
(x4 + x2 + x + 1)
=[(x4 + x2 + x + 1)1 mod (x8 + x4 + x3 + x + 1)]
t3(x) a3(x)  q(x)*b3(x)
=(x6 + x4 + x3 + x2 + x + 1) ) 5F16
(x8 + x4 + x3 + x + 1  (x4 + x2 + x + 1)(x4 + x2 + x + 1))
(x3 + x2 + x)
Job is successfully accomplished and this answer tallies with
6. [{a1(x), a2(x), a3(x)} {b1(x), b2(x), b3(x)}]
the look-up table procedure outlined in Section 3.
a1(x) 0,
Several algorithms for calculating the multiplicative inverse in
a2(x) 1,
GF(28) and comparing the speed/area tradeoffs for implementation
a3(x) (x4 + x2 + x + 1).
on a complex programmable logic device were investigated by [9]
7. [{b1(x), b2(x), b3(x)} {t1(x), t2(x), t3(x)}]
and the results indicate that look-up table method requires 50 nS
b1(x) 1,
and the extended Euclid algorithm takes 755 nS. Also the transistor
b2(x) (x4 + x2 + x + 1),
count for look-up table method is 6180 and that for the Extended
b3(x) (x3 + x2 + x).
Euclid algorithm is 10,714. It is up to the user to choose between
8. Goto 2 (accomplished, so iteration 2}
the two according to a particular application.

4. Conclusion and recommendation

Iteration 2:
2,3 Not applicable
The two available methods to find multiplicative inverse in
4. q(x) = quotient of a3(x)/b3(x)
4 2 þxþ1 GF(28) of the same number are used. Detailed working is given in
¼ x xþx
3 þx2 þx ¼ x þ 1
this paper. A comparison is made in terms of time, transistor count,
 M. Saeed, M. Saleem Mian / Computer Communications 31 (2008) 4117–4123 4123

effort, complexity. The look-up table method requires much less [3] H. Anton, C. Rorres, Elementary Linear Algebra, John Wiley & Sons, Inc.,
Singapore, 1991. pp. 690–695.
transistors than Euclid’s algorithm and it is much faster too. This
[4] J. Pieprzyk, T. Hardjono, J. Seberry, Fundamentals of Computer Security,
paper puts together important material on this topic in one paper. Springer-Verlag Berlin, Heidelberg, Germany, 2003. pp. 34–35.
The look-up table method involves less effort and makes use of [5] M.B. Nathanson, Methods in Number Theory, Springer-Verlag, New York, 1994.
simple equations; whereas, the use of extended Euclid’s algorithm pp. 17–19.
[6] M.Y. Rhee, Cryptography and Secure Communications, McGraw-Hill Book
is very attractive for incorporating it in the implementation of new Company, Singapore, 1994. pp. 176–178, 187.
and the existing crypto-graphic techniques through software. Since [7] N. Koblitz, A Course in Number Theory and Cryptography, Springer-Verlag,
the look-up table method is much faster and requires less hard- New York, 1994. pp. 12–14.
[8] N.R. Wagner, The Laws of Cryptography: The Finite Field GF(28), File://
ware and hence consumes less power should be preferred over Eu- E:ngfnThe Laws of Cryptography: The Finite Field GF(28).htm, 2007, pp. 1–8.
clid’s algorithm. [9] R.W. Ward, T.C.A. Molteno, Efficient Hardware Calculation of Inverses in
GF(28), Physics Department, University of Otago, Box 56, Dunedin, New
Zealand, pp. 1–6. Available from: <tim@physics.ontago.ac.nz>.
References [10] T. Koshy, Elementary Number Theory with Applications, Elsevier India
(Private) Limited, 17-A/1, Main Ring Road, Lajpat Nagar-IV, New Delhi 110
[1] B. Schneier, Applied Cryptography, Replika Press (Pvt). Ltd, India, 2006. pp. 024, India, 2002, pp. 161–164.
242–246. [11] W. Stallings, Cryptography and Network Security, Prentice-Hall of India
[2] D. Stinson, Cryptography: Theory and Practice, Boca Raton, FL, CRC Press, 2002. Private Limited, M-97, Connaught Circus, New Delhi 110 001, India, 2000,
pp. 10–12, 116–120. pp. 104–134.