Cryptography and Network Security (4th Edition)

Briefly define a group.

Briefly define a ring.

Briefly define a field.

What does it mean to say that b is a divisor of a?

What is the difference between modular arithmetic and ordinary arithmetic?

List three classes of polynomial arithmetic.

For the group S_n of all permutations of n distinct symbols,

1. What is the number of elements in S_n?

2. Show that S_n is not abelian for n > 2.

Does the set of residue classes modulo 3 form a group

1. with respect to addition?

2. with respect to multiplication?

Consider the set S = {a, b} with addition and multiplication defined by the tables:

Is S a ring? Justify your answer.

Reformulate Equation (4.1), removing the restriction that a is a nonnegative integer. That is, let a be any integer.

Draw a figure similar to Figure 4.2 for a < 0.

Find integers x such that

1. 5x 4 (mod 3)

2. 7x 6 (mod 5)

3. 9x 8 (mod 7)

In this text we assume that the modulus is a positive integer. But the definition of the expression a mod n also makes perfect sense if n is negative. Determine the following:

1. 5 mod 3

2. 5 mod 3

3. 5 mod 3

4. 5 mod 3

A modulus of 0 does not fit the definition, but is defined by convention as follows: a mod 0 = a. With this definition in mind, what does the following expression mean: a

In Section 4.2, we define the congruence relationship as follows: Two integers a and b are said to be congruent modulo n, if (a mod n) = (b mod n). We then proved that a n) if n|(a b). Some texts on number theory use this latter relationship as the definition of congruence: Two integers a and b are said to be congruent modulo n, if n|(a b). Using this latter definition as the starting point, prove that if (a mod n) = (b mod n), then n divides (a b).

What is the smallest positive integer that has exactly k divisors, for 1 6?

Prove the following:

1. a n) implies b n)

2. a n) and b n) imply a n)

Prove the following:

1. [(a mod n) (b mod n)] mod n = (a b) mod n

2. [(a mod n) x (b mod n)] mod n = (a x b) mod n

Find the multiplicative inverse of each nonzero element in Z₅.

Show that an integer N is congruent modulo 9 to the sum of its decimal digits. For example, 475 4 + 7 + 5 16 1 + 6 7 (mod 9). This is the basis for the familiar procedure of "casting out 9s" when checking computations in arithmetic.

1. Determine gcd(24140, 16762).

2. Determine gcd(4655, 12075).

The purpose of this problem is to set an upper bound on the number of iterations of the Euclidean algorithm.

1. Suppose that m = qn + r with q > 0 and 0 n. Show that m/2 > r.

2. Let A_t be the value of A in the Euclidean algorithm after the ith iteration. Show that

3. Show that if m, n, and N are integers with 1 n, 2^{N steps to find gcd(m, n).}

The Euclidean algorithm has been known for over 2000 years and has always been a favorite among number theorists. After these many years, there is now a potential competitor, invented by J. Stein in 1961. Stein's algorithms is as follows. Determine gcd(A, B) with A, B 1.

Continue to step n + 1.

1. To get a feel for the two algorithms, compute gcd(2152, 764) using both the Euclidean and Stein's algorithm.

2. What is the apparent advantage of Stein's algorithm over the Euclidean algorithm?

1. Show that if Stein's algorithm does not stop before the nth step, then

   C_n+1 x gcd(A_n+1, B_n+1) = C_n x gcd(A_n, B_n)

2. Show that if the algorithm does not stop before step (n 1), then

3. Show that if 1 2^{N steps to find gcd(m, n). Thus, Stein's algorithm works in roughly the same number of steps as the Euclidean algorithm.}

4. Demonstrate that Stein's algorithm does indeed return gcd(A, B).

Using the extended Euclidean algorithm, find the multiplicative inverse of

1. 1234 mod 4321

2. 24140 mod 40902

3. 550 mod 1769

Develop a set of tables similar to Table 4.3 for GF(5).

Demonstrate that the set of polynomials whose coefficients form a field is a ring.

Demonstrate whether each of these statements is true or false for polynomials over a field:

1. The product of monic polynomials is monic.

2. The product of polynomials of degrees m and n has degree m + n

3. The sum of polynomials of degrees m and n has degree max[m, n].

For polynomial arithmetic with coefficients in Z₁₀, perform the following calculations:

1. (7x + 2) (x² + 5)

2. (6x² + x + 3) x (5x² + 2)

Determine which of the following are reducible over GF(2):

1. x³ + 1

2. x³ + x² + 1

3. x⁴ + 1 (be careful)

Determine the gcd of the following pairs of polynomials:

1. x³ + x + 1 and x² + x + 1 over GF(2)

2. x³ x + 1 and x² + 1 over GF(3)

3. x⁵ + x⁴ + x³ x² x + 1 and x³ + x² + x + 1 over GF(3)

4. x⁵ + 88x⁴ + 73x³ + 83x² + 51x + 67 and x³ + 97x² + 40x + 38 over GF(101)

Develop a set of tables similar to Table 4.6 for GF(4) with m(x) = x⁴ + x + 1.

Determine the multiplicative inverse of x³ + x + 1 in GF(2⁴), with m(x) = x⁴ + x + 1.

Develop a table similar to Table 4.8 for GF(2⁴) with m(x) = x⁴ + x + 1.

Write a simple four-function calculator in GF(2⁴). You may use table lookups for the multiplicative inverses.

Write a simple four-function calculator in GF(2⁸). You should compute the multiplicative inverses on the fly.