Discrete Logarithms and Diffie-Hellman

Prev: Introduction Next: Integer Factorization and RSA

Exercises

Section 2.1. Diffie-Hellman and RSA

2.1

Write a one page essay giving arguments, both pro and con, for the following assertion:

If the government is able to convince a court that there is a valid reason for their request, then they should have access to an individual’s private keys (even without the individual’s knowledge), in the same way that the government is allowed to conduct court authorized secret wiretaps in cases of suspected criminal activity or threats to national security.

Based on your arguments, would you support or oppose the government being given this power? How about without court oversight? The idea that all private keys should be stored at a secure central location and be accessible to government agencies (with or without suitably stringent legal conditions) is called key escrow.

2.2

Research and write a one to two page essay on the classification of cryptographic algorithms as munitions under ITAR (International Traffic in Arms Regulations). How does that act define “export”? What are the potential fines and jail terms for those convicted of violating the Arms Export Control Act? Would teaching non-classified cryptographic algorithms to a college class that includes non-US citizens be considered a form of export? How has US government policy changed from the early 1990s to the present?

Section 2.2. The Discrete Logarithm Problem

2.3

Let $g$ be a primitive root for ${\mathbb{F}}_p$.

(a) Suppose that $x=a$ and $x=b$ are both integer solutions to the congruence $g^x\equiv h(\mathrm{mod}p)$. Prove that $a\equiv b(\mathrm{mod}p-1)$. Explain why this implies that the map (2.1) on page 65 is well-defined.

(b) Prove that

$${\log }_g(h_1{h}_2)={\log }_g(h_1)+{\log }_g(h_2)$$

for all $h_1,h_2\in {\mathbb{F}}_p^{\ast }$.

(c) Prove that

$${\log }_g(h^n)=n{\log }_g(h)$$

for all $h\in {\mathbb{F}}_p^{\ast }$ and $n\in \mathbb{Z}$.

2.4

Compute the following discrete logarithms.

(a) ${\log }_2(13)$ for the prime $23$, i.e., $p=23$, $g=2$, and you must solve the congruence $2^x\equiv 13(\mathrm{mod}23)$.

(b) ${\log }_{10}(22)$ for the prime $p=47$.

(c) ${\log }_{627}(608)$ for the prime $p=941$. Hint: Look in the second column of Table 2.1 on page 66.

2.5

Let $p$ be an odd prime and let $g$ be a primitive root modulo $p$. Prove that $a$ has a square root modulo $p$ if and only if its discrete logarithm ${\log }_g(a)$ modulo $p-1$ is even.

Section 2.3. Diffie-Hellman Key Exchange

2.6

Alice and Bob agree to use the prime $p=1373$ and the base $g=2$ for a Diffie-Hellman key exchange. Alice sends Bob the value $A=974$. Bob asks your assistance, so you tell him to use the secret exponent $b=871$. What value $B$ should Bob send to Alice, and what is their secret shared value? Can you figure out Alice’s secret exponent?

2.7

Let $p$ be a prime and let $g$ be an integer. The Decision Diffie-Hellman Problem is as follows. Suppose that you are given three numbers $A$, $B$, and $C$, and suppose that $A$ and $B$ are equal to

$$A\equiv g^a(\mathrm{mod}p)\text{and}B\equiv g^b(\mathrm{mod}p),$$

but that you do not necessarily know the values of the exponents $a$ and $b$. Determine whether $C$ is equal to $g^{ab}(\mathrm{mod}p)$. Notice that this is different from the Diffie-Hellman problem described on page 69. The Diffie-Hellman problem asks you to actually compute the value of $g^{ab}$.

(a) Prove that an algorithm that solves the Diffie-Hellman problem can be used to solve the decision Diffie-Hellman problem.

(b) Do you think that the decision Diffie-Hellman problem is hard or easy? Why?

See Exercise 6.40 for a related example in which the decision problem is easy, but it is believed that the associated computational problem is hard.

Section 2.4. The Elgamal Public Key Cryptosystem

2.8

Alice and Bob agree to use the prime $p=1373$ and the base $g=2$ for communications using the Elgamal public key cryptosystem.

(a) Alice chooses $a=947$ as her private key. What is the value of her public key $A$?

(b) Bob chooses $b=716$ as his private key, so his public key is

$$B\equiv 2^{716}\equiv 469(\mathrm{mod}1373).$$

Alice encrypts the message $m=583$ using the random element $k=877$. What is the ciphertext $(c_1,c_2)$ that Alice sends to Bob?

(c) Alice decides to choose a new private key $a=299$ with associated public key $A\equiv 2^{299}\equiv 34(\mathrm{mod}1373)$. Bob encrypts a message using Alice’s public key and sends her the ciphertext $(c_1,c_2)=(661,1325)$. Decrypt the message.

(d) Now Bob chooses a new private key and publishes the associated public key $B=893$. Alice encrypts a message using this public key and sends the ciphertext $(c_1,c_2)=(693,793)$ to Bob. Eve intercepts the transmission. Help Eve by solving the discrete logarithm problem $2^b\equiv 893(\mathrm{mod}1373)$ and using the value of $b$ to decrypt the message.

2.9

Suppose that Eve is able to solve the Diffie-Hellman problem described on page 69. More precisely, assume that if Eve is given two powers $g^u$ and $g^v\mathrm{mod}p$, then she is able to compute $g^{uv}\mathrm{mod}p$. Show that Eve can break the Elgamal PKC.

2.10

The exercise describes a public key cryptosystem that requires Bob and Alice to exchange several messages. We illustrate the system with an example.

Bob and Alice fix a publicly known prime $p=32611$, and all of the other numbers used are private. Alice takes her message $m=11111$, chooses a random exponent $a=3589$, and sends the number $u=m^a(\mathrm{mod}p)=15950$ to Bob. Bob chooses a random exponent $b=4037$ and sends $v=u^b(\mathrm{mod}p)=15422$ back to Alice. Alice then computes $w=v^{15619}\equiv 27257(\mathrm{mod}32611)$ and sends $w=27257$ to Bob. Finally, Bob computes $w^{31883}(\mathrm{mod}32611)$ and recovers the value $11111$ of Alice’s message.

(a) Explain why this algorithm works. In particular, Alice uses the numbers $a=3589$ and $15619$ as exponents. How are they related? Similarly, how are Bob’s exponents $b=4037$ and $31883$ related?

(b) Formulate a general version of this cryptosystem, i.e., using variables, and show that it works in general.

(c) What is the disadvantage of this cryptosystem over Elgamal? Hint: How many times must Alice and Bob exchange data?

(d) Are there any advantages of this cryptosystem over Elgamal? In particular, can Eve break it if she can solve the discrete logarithm problem? Can Eve break it if she can solve the Diffie-Hellman problem?

Section 2.5. An Overview of the Theory of Groups

2.11

The group $S_3$ consists of the following six distinct elements

$$e,\sigma ,{\sigma }^2,\tau ,\sigma \tau ,{\sigma }^2\tau ,$$

where $e$ is the identity element and multiplication is performed using the rules

$${\sigma }^3=e,{\tau }^2=e,\tau \sigma ={\sigma }^2\tau .$$

Compute the following values in the group $S_3$:

(a) $\tau {\sigma }^2$

(b) $\tau (\sigma \tau )$

(c) $(\sigma \tau )(\sigma \tau )$

(d) $(\sigma \tau )({\sigma }^2\tau )$

Is $S_3$ a commutative group?

2.12

Let $G$ be a group, let $d\ge 1$ be an integer, and define a subset of $G$ by

$$G[d]=\{g\in G:g^d=e\}.$$

(a) Prove that if $g$ is in $G[d]$, then $g^{-1}$ is in $G[d]$.

(b) Suppose that $G$ is commutative. Prove that if $g_1$ and $g_2$ are in $G[d]$, then their product $g_1\cdot g_2$ is in $G[d]$.

(c) Deduce that if $G$ is commutative, then $G[d]$ is a group.

(d) Show by an example that if $G$ is not a commutative group, then $G[d]$ need not be a group. Hint: Use Exercise 2.11.

2.13

Let $G$ and $H$ be groups. A function $\varphi :G\to H$ is called a group homomorphism if it satisfies

$$\varphi (g_1\cdot g_2)=\varphi (g_1)\cdot \varphi (g_2)\text{for all }{g}_1,g_2\in G.$$

Note that the product $g_1\cdot g_2$ uses the group law in the group $G$, while the product $\varphi (g_1)\cdot \varphi (g_2)$ uses the group law in the group $H$.

(a) Let $e_G$ be the identity element of $G$, let $e_H$ be the identity element of $H$, and let $g\in G$. Prove that

$$\varphi (e_G)=e_H\text{and}\varphi (g^{-1})=\varphi (g{)}^{-1}.$$

(b) Let $G$ be a commutative group. Prove that the map $\varphi :G\to G$ defined by $\varphi (g)=g^2$ is a homomorphism. Give an example of a noncommutative group for which this map is not a homomorphism.

(c) Same question as (b) for the map $\varphi (g)=g^{-1}$.

2.14

Prove that each of the following maps is a group homomorphism.

(a) The map $\varphi :\mathbb{Z}\to \mathbb{Z}/N\mathbb{Z}$ that sends $a\in \mathbb{Z}$ to $a\mathrm{mod}N$ in $\mathbb{Z}/N\mathbb{Z}$.

(b) The map $\varphi :{\mathbb{R}}^{\ast }\to {\mathrm{GL}}_2(\mathbb{R})$ defined by

$$\varphi (a)=\left(\begin{array}{cc}a& 0\\ 0& a^{-1}\end{array}\right).$$

(c) The discrete logarithm map ${\log }_g:{\mathbb{F}}_p^{\ast }\to \mathbb{Z}/(p-1)\mathbb{Z}$, where $g$ is a primitive root modulo $p$.

2.15

(a) Prove that ${\mathrm{GL}}_2({\mathbb{F}}_p)$ is a group.

(b) Show that ${\mathrm{GL}}_2({\mathbb{F}}_p)$ is a noncommutative group for every prime $p$.

(c) Describe ${\mathrm{GL}}_2({\mathbb{F}}_2)$ completely. That is, list its elements and describe the multiplication table.

(d) How many elements are there in the group ${\mathrm{GL}}_2({\mathbb{F}}_p)$?

(e) How many elements are there in the group ${\mathrm{GL}}_n({\mathbb{F}}_p)$?

Section 2.6. How Hard Is the Discrete Logarithm Problem?

2.16

Verify the following assertions from Example 2.16.

(a) $x^2+x=O(x^2)$.

(b) $5+6x^2-37x^5=O(x^5)$.

(c) $k^{300}=O(2^k)$.

(d) $(\ln k{)}^{375}=O(k^{0.001})$.

(e) $k^2{2}^k=O(e^{2k})$.

(f) $N^{10}{2}^N=O(e^N)$.

Section 2.7. A Collision Algorithm for the DLP

2.17

Use Shanks’s babystep-giantstep method to solve the following discrete logarithm problems. For (b) and (c), you may want to write a computer program implementing Shanks’s algorithm.

(a) $11^x=21$ in ${\mathbb{F}}_{71}$.

(b) $156^x=116$ in ${\mathbb{F}}_{593}$.

(c) $650^x=2213$ in ${\mathbb{F}}_{3571}$.

Section 2.8. The Chinese Remainder Theorem

2.18

Solve each of the following simultaneous systems of congruences, or explain why no solution exists.

(a) $x\equiv 3(\mathrm{mod}7)$ and $x\equiv 4(\mathrm{mod}9)$.

(b) $x\equiv 137(\mathrm{mod}423)$ and $x\equiv 87(\mathrm{mod}191)$.

(c) $x\equiv 133(\mathrm{mod}451)$ and $x\equiv 237(\mathrm{mod}697)$.

(d) $x\equiv 5(\mathrm{mod}9)$, $x\equiv 6(\mathrm{mod}10)$, and $x\equiv 7(\mathrm{mod}11)$.

(e) $x\equiv 37(\mathrm{mod}43)$, $x\equiv 22(\mathrm{mod}49)$, and $x\equiv 18(\mathrm{mod}71)$.

2.19

Solve the 1700-year-old Chinese remainder problem from the Sun Tzu Suan Ching stated on page 84.

2.20

Let $a,b,m,n$ be integers with $\gcd (m,n)=1$. Let

$$c\equiv (b-a)\cdot m^{-1}(\mathrm{mod}n).$$

Prove that $x=a+cm$ is a solution to

$$x\equiv a(\mathrm{mod}m)\text{and}x\equiv b(\mathrm{mod}n),\text{\hspace{1em}(2.24)}$$

and that every solution to (2.24) has the form $x=a+cm+ymn$ for some $y\in \mathbb{Z}$.

2.21

(a) Let $a,b,c$ be positive integers and suppose that

$$a\mid c,b\mid c,\text{and}\gcd (a,b)=1.$$

Prove that $ab\mid c$.

(b) Let $x=c$ and $x=c^{\prime }$ be two solutions to the system of simultaneous congruences (2.7) in the Chinese remainder theorem (Theorem 2.24). Prove that

$$c\equiv c^{\prime }(\mathrm{mod}{m}_1{m}_2\cdots m_k).$$

2.22

For those who have studied ring theory, this exercise sketches a short proof of the Chinese remainder theorem. Let $m_1,\dots ,m_k$ be integers and let $m=m_1{m}_2\cdots m_k$ be their product.

(a) Prove that the map

$$\begin{array}{rl}\mathbb{Z}/m\mathbb{Z}& ⟶\mathbb{Z}/m_1\mathbb{Z}\times \mathbb{Z}/m_2\mathbb{Z}\times \cdots \times \mathbb{Z}/m_k\mathbb{Z},\\ a\mathrm{mod}m& ⟼(a\mathrm{mod}{m}_1,a\mathrm{mod}{m}_2,\dots ,a\mathrm{mod}{m}_k)\end{array}\text{\hspace{1em}(2.25)}$$

is a well-defined homomorphism of rings. Hint: First define a homomorphism from $\mathbb{Z}$ to the right-hand side of (2.25), and then show that $m\mathbb{Z}$ is in the kernel.

(b) Assume that $m_1,\dots ,m_k$ are pairwise relatively prime. Prove that the map given by (2.25) is one-to-one. Hint: What is the kernel?

(c) Continuing with the assumption that the numbers $m_1,\dots ,m_k$ are pairwise relatively prime, prove that the map (2.25) is onto. Hint: Use (b) and count the size of both sides.

(d) Explain why the Chinese remainder theorem (Theorem 2.24) is equivalent to the assertion that (b) and (c) are true.

2.23

Use the method described in Sect. 2.8.1 to find square roots modulo the following composite moduli.

(a) Find a square root of $340$ modulo $437$. Note that $437=19\cdot 23$.

(b) Find a square root of $253$ modulo $3143$.

(c) Find four square roots of $2833$ modulo $4189$. The modulus factors as $4189=59\cdot 71$. Note that your four square roots should be distinct modulo $4189$.

(d) Find eight square roots of $813$ modulo $868$.

2.24

Let $p$ be an odd prime, let $a$ be an integer that is not divisible by $p$, and let $b$ be a square root of $a$ modulo $p$. This exercise investigates the square root of $a$ modulo powers of $p$.

(a) Prove that for some choice of $k$, the number $b+kp$ is a square root of $a$ modulo $p^2$, i.e., $(b+kp{)}^2\equiv a(\mathrm{mod}{p}^2)$.

(b) The number $b=537$ is a square root of $a=476$ modulo the prime $p=1291$. Use the idea in (a) to compute a square root of $476$ modulo $p^2$.

(c) Suppose that $b$ is a square root of $a$ modulo $p^n$. Prove that for some choice of $j$, the number $b+j{p}^n$ is a square root of $a$ modulo $p^{n+1}$.

(d) Explain why (c) implies the following statement: If $p$ is an odd prime and if $a$ has a square root modulo $p$, then $a$ has a square root modulo $p^n$ for every power of $p$. Is this true if $p=2$?

(e) Use the method in (c) to compute the square root of $3$ modulo $13^3$, given that $9^2\equiv 3(\mathrm{mod}13)$.

2.25

Suppose $n=pq$ with $p$ and $q$ distinct odd primes.

(a) Suppose that $\gcd (a,pq)=1$. Prove that if the equation $x^2\equiv a(\mathrm{mod}n)$ has any solutions, then it has four solutions.

(b) Suppose that you had a machine that could find all four solutions for some given $a$. How could you use this machine to factor $n$?

Section 2.9. The Pohlig-Hellman Algorithm

2.26

Let ${\mathbb{F}}_p$ be a finite field and let $N\mid p-1$. Prove that ${\mathbb{F}}_p^{\ast }$ has an element of order $N$. This is true in particular for any prime power that divides $p-1$. Hint: Use the fact that ${\mathbb{F}}_p^{\ast }$ has a primitive root.

2.27

Write out your own proof that the Pohlig-Hellman algorithm works in the particular case that $p-1=q_1\cdot q_2$ is a product of two distinct primes. This provides a good opportunity for you to understand how the proof works and to get a feel for how it was discovered.

2.28

Use the Pohlig-Hellman algorithm (Theorem 2.31) to solve the discrete logarithm problem

$$g^x=a\text{in }{\mathbb{F}}_p$$

in each of the following cases.

(a) $p=433$, $g=7$, $a=166$.

(b) $p=746497$, $g=10$, $a=243278$.

(c) $p=41022299$, $g=2$, $a=39183497$. Hint: $p=2\cdot 29^5+1$.

(d) $p=1291799$, $g=17$, $a=192988$. Hint: $p-1$ has a factor of $709$.

Section 2.10. Rings, Quotient Rings, Polynomial Rings, and Finite Fields

2.29

Let $R$ be a ring with the property that the only way that a product $a\cdot b$ can be $0$ is if $a=0$ or $b=0$. In the terminology of Example 2.55, the ring $R$ has no zero divisors. Suppose further that $R$ has only finitely many elements. Prove that $R$ is a field. Hint: Let $a\in R$ with $a\ne 0$. What can you say about the map $R\to R$ defined by $b\mapsto a\cdot b$?

2.30

Let $R$ be a ring. Prove the following properties of $R$ directly from the ring axioms described in Sect. 2.10.1.

(a) Prove that the additive identity element $0\in R$ is unique, i.e., prove that there is only one element in $R$ satisfying $0+a=a+0=a$ for every $a\in R$.

(b) Prove that the multiplicative identity element $1\in R$ is unique.

(c) Prove that every element of $R$ has a unique additive inverse.

(d) Prove that $0\cdot a=a\cdot 0=0$ for all $a\in R$.

(e) We denote the additive inverse of $a$ by $-a$. Prove that $-(-a)=a$.

(f) Let $-1$ be the additive inverse of the multiplicative identity element $1\in R$. Prove that $(-1)\cdot (-1)=1$.

(g) Prove that $b\mid 0$ for every nonzero $b\in R$.

(h) Prove that an element of $R$ has at most one multiplicative inverse.

2.31

Let $R$ and $S$ be rings. A function $\varphi :R\to S$ is called a ring homomorphism if it satisfies

$$\varphi (a+b)=\varphi (a)+\varphi (b)\text{and}\varphi (a\cdot b)=\varphi (a)\cdot \varphi (b)\text{for all }a,b\in R.$$

(a) Let $0_R$, $0_S$, $1_R$ and $1_S$ denote the additive and multiplicative identities of $R$ and $S$, respectively. Prove that

$$\varphi (0_R)=0_S,\varphi (1_R)=1_S,\varphi (-a)=-\varphi (a),\varphi (a^{-1})=\varphi (a{)}^{-1},$$

where the last equality holds for those $a\in R$ that have a multiplicative inverse.

(b) Let $p$ be a prime, and let $R$ be a ring with the property that $pa=0$ for every $a\in R$. Here $pa$ means to add $a$ to itself $p$ times. Prove that the map

$$\varphi :R⟶R,\varphi (a)=a^p$$

is a ring homomorphism. It is called the Frobenius homomorphism.

2.32

Prove Proposition 2.41.

2.33

Prove Proposition 2.43. Hint: First use Exercise 2.32 to prove that the congruence classes $a+b$ and $a\cdot b$ depend only on the congruence classes of $a$ and $b$.

2.34

Let $F$ be a field and let $a$ and $b$ be nonzero polynomials in $F[x]$.

(a) Prove that $\mathrm{deg}(a\cdot b)=\mathrm{deg}(a)+\mathrm{deg}(b)$.

(b) Prove that $a$ has a multiplicative inverse in $F[x]$ if and only if $a$ is in $F$, i.e., if and only if $a$ is a constant polynomial.

(c) Prove that every nonzero element of $F[x]$ can be factored into a product of irreducible polynomials. Hint: Use (a), (b), and induction on the degree of the polynomial.

(d) Let $R$ be the ring $\mathbb{Z}/6\mathbb{Z}$. Give an example to show that (a) is false for some polynomials $a$ and $b$ in $R[x]$.

2.35

Let $a$ and $b$ be the polynomials

$$\begin{array}{rl}a& =x^5+3x^4-5x^3-3x^2+2x+2,\\ b& =x^5+x^4-2x^3+4x^2+x+5.\end{array}$$

Use the Euclidean algorithm to compute $\gcd (a,b)$ in each of the following rings.

(a) ${\mathbb{F}}_2[x]$

(b) ${\mathbb{F}}_3[x]$

(c) ${\mathbb{F}}_5[x]$

(d) ${\mathbb{F}}_7[x]$

2.36

Continuing with the same polynomials $a$ and $b$ as in Exercise 2.35, for each of the polynomial rings (a)-(d) in Exercise 2.35, find polynomials $u$ and $v$ satisfying

$$a\cdot u+b\cdot v=\gcd (a,b).$$

2.37

Prove that the polynomial $x^3+x+1$ is irreducible in ${\mathbb{F}}_2[x]$. Hint: Think about what a factorization would have to look like.

2.38

The multiplication table for the field ${\mathbb{F}}_2[x]/(x^3+x+1)$ is given in Table 2.5, but we have omitted fourteen entries. Fill in the missing entries. This is the field described in Example 2.57. You can download and print a copy of Table 2.5 at www.math.brown.edu/~jhs/MathCrypto/Table2.5.pdf.

$\cdot$	$0$	$1$	$x$	$x^2$	$1+x$	$1+x^2$	$x+x^2$	$1+x+x^2$
$0$	$0$	$0$	$0$	$0$	$0$	$0$	$0$	$0$
$1$	$0$	$1$	$x$			$1+x^2$	$x+x^2$	$1+x+x^2$
$x$	$0$	$x$	$x^2$		$x+x^2$	$1$		$1+x^2$
$x^2$	$0$			$x+x^2$	$1+x+x^2$	$x$	$1+x^2$	$1$
$1+x$	$0$		$x+x^2$	$1+x+x^2$	$1+x^2$		$1$	$x$
$1+x^2$	$0$	$1+x^2$	$1$	$x$		$1+x+x^2$	$1+x$
$x+x^2$	$0$	$x+x^2$		$1+x^2$	$1$	$1+x$	$x$
$1+x+x^2$	$0$	$1+x+x^2$	$1+x^2$	$1$	$x$			$1+x$

2.39

The field ${\mathbb{F}}_7[x]/(x^2+1)$ is a field with $49$ elements, which for the moment we denote by ${\mathbb{F}}_{49}$. See Example 2.58 for a convenient way to work with ${\mathbb{F}}_{49}$.

(a) Is $2+5x$ a primitive root in ${\mathbb{F}}_{49}$?

(b) Is $2+x$ a primitive root in ${\mathbb{F}}_{49}$?

(c) Is $1+x$ a primitive root in ${\mathbb{F}}_{49}$?

Hint: Lagrange’s theorem says that the order of $u\in {\mathbb{F}}_{49}$ must divide $48$. So if $u^k\ne 1$ for all proper divisors $k$ of $48$, then $u$ is a primitive root.

2.40

Let $p$ be a prime number and let $e\ge 2$. The quotient ring $\mathbb{Z}/p^e\mathbb{Z}$ and the finite field ${\mathbb{F}}_{p^e}$ are both rings and both have the same number of elements. Describe some ways in which they are intrinsically different.

2.41

Let $F$ be a finite field.

(a) Prove that there is an integer $m\ge 1$ such that if we add $1$ to itself $m$ times,

$$\underset{m\text{ ones}}{\underbrace{1+1+\cdots +1}},$$

then we get $0$. Note that here $1$ and $0$ are the multiplicative and additive identity elements of the field $F$. If the notation is confusing, you can let $u$ and $z$ be the multiplicative and additive identity elements of $F$, and then you need to prove that $u+u+\cdots +u=z$. Hint: Since $F$ is finite, the numbers $1$, $1+1$, $1+1+1$, … cannot all be different.

(b) Let $m$ be the smallest positive integer with the property described in (a). Prove that $m$ is prime. Hint: If $m$ factors, show that there are nonzero elements in $F$ whose product is zero, so $F$ cannot be a field. This prime is called the characteristic of the field $F$.

(c) Let $p$ be the characteristic of $F$. Prove that $F$ is a finite-dimensional vector space over the field ${\mathbb{F}}_p$ of $p$ elements.

(d) Use (c) to deduce that $F$ has $p^d$ elements for some $d\ge 1$.