Discrete Mathematics and Probability Theory

Definitions and Theorems

Graph Theory

Graph: A graph $G$ is a pair $(V,E)$ where $V$ is a set of vertices and $E$ a set of edges. An edge in an undirected graph is a pair of vertices $\{u,v\}$, while in a directed graph it is an ordered pair $(u,v)$.

---

Incident: We say that an edge $e=\{u,v\}$ is incident on vertices $u$ and $v$, and that $u$ and $v$ are neighbors or adjacent.

---

Degree: If $G=(V,E)$ is undirected, then the degree of a vertex $v\in V$ is the number of edges incident to $v$, i.e.,

$$\mathrm{deg}(v)=|\{v\in V:\{u,v\}\in E\}|.$$

A directed graph, however, has two different notions of degree due to the directions on the edges. Specifically, the in-degree of a vertex $u$ is the number of edges from other vertices to $u$, and the out-degree is the number of edges from $u$ to other vertices.

---

Paths, walks and cycles: A path in a graph $G$ is a sequence of edges $\{v_1,v_2\},\{v_3,v_4\},...,\{v_{n-1},v_n\}$. In this case we say there is a path between $v_1$ and $v_n$. We assume a path is simple, meaning $v_1,...,v_n$ are distinct.

---

Modular Arithmetic

Fermat’s Little Theorem: Let ${\mathbf{GF}}_p$ be a Galois Field modulo a prime $p$. Then

$$\forall x\in {\mathbf{GF}}_p\backslash \{0\}:x^{p-1}\equiv 1(\mathrm{mod}p)$$

where ${\mathbf{GF}}_p\backslash \{0\}=\{1,2,...,p-1\}$ is the set of nonzero elements in ${\mathbf{GF}}_p$.

---

Polynomials Over Finite Fields

Polynomial: A degree-$d$ polynomial $f(x)$ is a function of the form:

$$f(x)=a_d{x}^d+a_{d-1}{x}^{d-1}+\cdots +a_{1}x+a_0$$

We call $a_d,...,a_0$ the coefficients of the polynomial. A degree-$d$ polynomial is uniquely determined by its values at $d+1$ distinct points.

---

Galois Field: A Galois Field (or Finite Field) ${\mathbf{GF}}_n$ is a finite set of $n$ elements that together constitute a field.

$${\mathbf{GF}}_n=\{0,1,2,...,n-1\}.$$

When $n$ is prime we gain the unique property under modular arithmetic that guarantees the existence of a modular inverse for every element in the field. Thus we often work with Galois Fields modulo a prime $p$, and denote it ${\mathbf{GF}}_p$.

---

Polynomial Equivalence: Two polynomials $f(x)$ and $g(x)$ defined over ${\mathbf{GF}}_p$ are equivalent if:

$$\forall x\in {\mathbf{GF}}_p:f(x)\equiv g(x)(\mathrm{mod}p)$$

---

Lagrange Interpolation Given $d+1$ distinct points $(x_0,y_0),...,(x_d,y_d)$, there exists a unique polynomial $\mathbf{P}(x)$ of degree at most $d$ such that $\mathbf{P}(x_i)=y_i$ for all $i=0,...,d$. This polynomial can be recovered from the given $d+1$ points by first constructing the Lagrange basis polynomials ${\lambda }_i(x),...,{\lambda }_{d+1}(x)$, then using them to form a linear combination of the $y_i$ values to recover $\mathbf{P}(x)$:

$${\lambda }_i(x)=\frac{{\prod }_{j\ne i}(x-x_j)}{{\prod }_{j\ne i}(x_i-x_j)},\mathbf{P}(x)=\sum _{i=0}^{d+1}{y}_i{\lambda }_i(x)$$

Example: Lagrange Interpolation

Recover the $2$-degree polynomial $\mathbf{P}(x)$ from the $3$ points: $(1,1)$, $(2,2)$, and $(3,4)$.

We first construct the Lagrange basis polynomials ${\lambda }_1(x),...,{\lambda }_3(x)$:

$$\begin{array}{rl}{\lambda }_1(x)& =\frac{(x-2)(x-3)}{(1-2)(1-3)}=\frac{(x-2)(x-3)}{2}=\frac{1}{2}{x}^2-\frac{5}{2}x+3\\ {\lambda }_2(x)& =\frac{(x-1)(x-3)}{(2-1)(2-3)}=\frac{(x-1)(x-3)}{-1}=-x^2+4x-3\\ {\lambda }_3(x)& =\frac{(x-1)(x-2)}{(3-1)(3-2)}=\frac{(x-1)(x-2)}{2}=\frac{1}{2}{x}^2-\frac{3}{2}x+1\end{array}$$

We can then recover $\mathbf{P}(x)$ by

$$\begin{array}{rl}\mathbf{P}(x)& =y_1{\lambda }_1(x)+y_2{\lambda }_2(x)+y_3{\lambda }_3(x)\\ & =1\underset{{\lambda }_1(x)}{\underbrace{\left(\frac{1}{2}{x}^2-\frac{5}{2}x+3\right)}}+2\underset{{\lambda }_2(x)}{\underbrace{\left(-x^2+4x-3\right)}}+4\underset{{\lambda }_3(x)}{\underbrace{\left(\frac{1}{2}{x}^2-\frac{3}{2}x+1\right)}}\\ & =\frac{1}{2}{x}^2-\frac{5}{2}x+3-{\cancel{2x}}^2+8x-6+\cancel{2x^2}-6x+4\\ & =\frac{1}{2}{x}^2-\frac{5}{2}x+2x+1\\ & =\frac{1}{2}{x}^2-\frac{1}{2}x+1\end{array}$$

The Many Applications of Polynomials

Secret Sharing

Assume we have a secret $s$ that we wish to distribute among $n$ parties such that any $k$ of them working together can recover the secret, but any less than $k$ cannot recover any information about $s$. Polynomials provide an elegant solution to this problem.

We work over ${\mathbf{GF}}_p$ for some prime $p$ where $p>n$ and $p>s$. To begin our secret-sharing scheme, we choose a random polynomial $\mathbf{P}(x)$ of degree $k-1$ such that $\mathbf{P}(0)=s$. We can then distribute shares of the secret $s_i$ to the $n$ parties by evaluating and then sending:

$$\mathbf{P}(i)=s_i\forall i\in \{1,...,n\}.$$

That is, party $1$ receives $s_1=\mathbf{P}(1)$, party $2$ receives $s_2=\mathbf{P}(2)$, and so on. Any $k$ parties can recover the secret $s$ by pooling their information together ($k$ points of $\mathbf{P}(x)$) and using Lagrange Interpolation to recover $\mathbf{P}(x)$. They can then evaluate $\mathbf{P}(0)$ to learn the secret $s$.

Reed-Solomon Codes

Reed-Solomon Codes are a class of error-correcting codes that are widely used in digital communication systems to protect against the loss or corruption of data packets. They are based on the theory of polynomials over Galois Fields modulo a prime $p$.

Erasure Errors

Say we have a message we wish to transmit along a wire that is prone to drop packets. Denote this message $(m_1,...,m_n)$, where each packet $m_i$ is represented as a value in ${\mathbf{GF}}_p$. (Note: each packet contains a header that indicates its position in the message; that is, the recipient can deduce exactly which packets were lost during transmission).

We want to guard against the possibility of there being at most $k$ errors (dropped packets). We can do this by constructing a polynomial $\mathbf{P}(x)$ of degree $n-1$ such that

$$\forall i\in \{1,...,n\}:\mathbf{P}(i)=m_i.$$

If there were no errors, then we could simply send $n$ points $(i,m_i)$ along the wire. However, if there are up to $k$ errors, we need to send an additional $k$ redundant points to help recover the original polynomial $\mathbf{P}(x)$. So in total we send $n+k$ evaluations of $\mathbf{P}(x)$, and call it the codeword $(c_1,...,c_{n+k})$ of $(m_1,...,m_n)$:

$$c_1=\mathbf{P}(1),c_2=\mathbf{P}(2),...,c_{n+k}=\mathbf{P}(n+k).$$

Recall that, given $n+1$ points, you can always construct a unique polynomial of degree $n$ that passes through all of them. Hence, even up to the case that $k$ packets are dropped, we can still recover the original polynomial $\mathbf{P}(x)$ since we possess $n+k$ points. Once we have $\mathbf{P}(x)$, we can recover the dropped packets by evaluating $\mathbf{P}(x)$ at the missing points (which, as stated above, the recipient knows from the packet headers).

General Errors

TODO!: Explain

What if we don’t immediately know the locations of the errors? Let $e_1,...,e_k$ be the $k$ locations at which errors occured. Denote $r_i$ as the recipient’s evaluation of $\mathbf{P}(i)$. So $\mathbf{P}(i)=r_i$ for all $i\notin \{e_1,...,e_k\}$.

Error-locator Polynomial:

$$E(x)=\prod _{i=1}^k(x-e_i)$$

Crucially, observe that:

$$\mathbf{P}(i)E(i)=r_{i}E(i)\forall i\in \{1,...,n+2k\}$$

This holds at points $i$ in which no error occured since at those points $P(i)=r_i$; and it is trivially true at points $i$ where errors occured since then $E(i)=0$. This is the true usefulness of the error-locator polynomial $E(x)$: the location $i$ of an error is guaranteed to be a root of $E(x)$.

Exercises

Equivalent Polynomials

Part A

Show that $f(x)=x^{p-1}$ and $g(x)=1$ are not equivalent polynomials under ${\mathbf{GF}}_p$.

Solution

At first glance — armed with Fermat’s Little Thoerem — it may seem that $f(x)$ should be equivalent to $g(x)$. However, note that FLT is stated as:

$$\forall x\in \{1,2,...,p-1\}:x^{p-1}\equiv 1(\mathrm{mod}p).$$

That is, $x$ is constrained to be in ${\mathbf{GF}}_p\backslash \{0\}$ (a nonzero element in the Galois Field). To prove then that $f(x)\not\equiv g(x)$, it suffices to evaluate both polynomials at $x=0$. Recall that we have $f(x)=x^{p-1}$ and $g(x)=1$, so then:

$$f(0)=0^{p-1}=0\ne g(0)=1.$$

This violates the property for $f(x)\equiv g(x)(\mathrm{mod}p)$, since

$$\exists x\in {\mathbf{GF}}_p:f(x)\not\equiv g(x)(\mathrm{mod}p)$$

namely, $x=0$, which is an element in ${\mathbf{GF}}_p$ (residue class of $p$) but is crucially excluded from the domain of $x$ in FLT. Hence $f(x)$ and $g(x)$ are not equivalent polynomials under ${\mathbf{GF}}_p$.

$$\text{\hspace{1em}■}$$

Part B

Use Fermat’s Little Theorem to find a polynomial with degree strictly less than $5$ that is equivalent to $f(x)=x^5$ over ${\mathbf{GF}}_5$; then find a polynomial with degree strictly less than $11$ that is equivalent to $g(x)=4x^{70}+9x^{11}+3$ over ${\mathbf{GF}}_{11}$.

Solution

Find $f_{†}(x)$ for $f(x)=x^5$ over ${\mathbf{GF}}_5$.

For the first part, we reduce $f(x)=x^5$ over ${\mathbf{GF}}_5$ using FLT. We have $p=5$, so then FLT tells us that:

$$\forall x\in {\mathbf{GF}}_5\backslash \{0\}:x^4\equiv 1(\mathrm{mod}5).$$

Meaning that any power of $x$ that is a multiple of $4$ will reduce to $1$. We can then rewrite the exponent $5$ in terms of $4$, since we know $x^4\equiv 1(\mathrm{mod}5)$:

$$\begin{array}{rl}{x}^5& \equiv x^4\cdot x\\ & \equiv 1\cdot x\\ & \equiv x(\mathrm{mod}5)\end{array}$$

Hence, the equivalent polynomial to $f(x)$ over ${\mathbf{GF}}_5$ with degree strictly less than $5$ is $f_{†}(x)=x$.

$$\text{\hspace{1em}■}$$

---

Find $g_{†}(x)$ for $g(x)=4x^{70}+9x^{11}+3$ over ${\mathbf{GF}}_{11}$.

Similarly, we reduce $g(x)$ over ${\mathbf{GF}}_{11}$ using Fermat’s Little Theorem. We have $p=11$, so then FLT tells us that:

$$\forall x\in {\mathbf{GF}}_{11}\backslash \{0\}:x^{10}\equiv 1(\mathrm{mod}11).$$

Meaning that we can reduce any exponent to a multiple of $10$, since any multiple of $10$ modulo $11$ will reduce to $1$. We reduce $x^{70}$ using this fact along with FLT:

$$\begin{array}{rl}70& \equiv 0(\mathrm{mod}10)\\ x^{70}& \equiv (x^{10}{)}^7\equiv 1^7\equiv 1(\mathrm{mod}11)\\ 4x^{70}& \equiv 4(\mathrm{mod}11)\end{array}\text{\hspace{1em}(FLT)}$$

Thus, $x^{70}$ reduces to $1(\mathrm{mod}11)$. Multiplying by its coefficient $4$, we get $4x^{70}\equiv 4(\mathrm{mod}11)$. We can similarly reduce $x^{11}$:

$$\begin{array}{rl}11& \equiv 1(\mathrm{mod}10)\\ x^{11}& \equiv x^1\equiv x(\mathrm{mod}11)\\ 9x^{11}& \equiv 9x(\mathrm{mod}11)\end{array}\text{\hspace{1em}(FLT)}$$

To find $g_{†}(x)$ then, we substitute these reduced terms back into $g(x)$:

$$\begin{array}{rl}{g}_{†}(x)& =\text{Reduced}(g(x))\\ & \equiv 4x^{70}+9x^{11}+3(\mathrm{mod}11)\\ & \equiv 4+9x+3\\ & \equiv 9x+7(\mathrm{mod}11)\end{array}$$

Hence, $g_{†}(x)=9x+7$ is the equivalent polynomial to $g(x)$ over ${\mathbf{GF}}_{11}$ with degree strictly less than $11$.

$$\text{\hspace{1em}■}$$

---

Part C

In ${\mathbf{GF}}_p$, prove that whenever $f(x)$ has degree $\ge p$, it is equivalent to some polynomial $f_{†}(x)$ with degree strictly less than $p$.

Solution

Let $f(x)={\sum }_{k=0}^d{a}_k{x}^k$, where $d\ge p$. Define

$$f_{†}(x)=\sum _{k=0}^{p-1}{b}_k{x}^k$$

such that

$$\forall x\in {\mathbf{GF}}_p:f(x)\equiv f_{†}(x)(\mathrm{mod}p).\text{\hspace{1em}(1)}$$

Recall from Fermat’s Little Theorem we have:

$$x^p\equiv x(\mathrm{mod}p)\text{\hspace{1em}(FLT)}$$

for all $x\in {\mathbf{GF}}_p\backslash \{0\}$. So if $f(x)$ has terms of degree $\ge p$, we can reduce them using:

$$x^p\equiv x,x^{p+1}\equiv x^2,x^{p+2}\equiv x^3,\text{etc.}$$

The equivalence in $(1)$ then follows from the fact that every exponent $k\ge p$ can be reduced modulo $p$ using the identity $x^p\equiv x(\mathrm{mod}p)$. This ensures that any polynomial in ${\mathbf{GF}}_p$ with degree $\ge p$ has an equivalent polynomial with degree strictly less than $p$.

$$\text{\hspace{1em}■}$$

Secret Sharing

Part A

A secret number $s$ is required to launch a rocket, and Alice distributed the values $(1,p(1)),(2,p(2)),...,(n+1,p(n+1))$ of a degree-$n$ polynomial $p(x)$ to a group ${\text{Bob}}_1,...,{\text{Bob}}_{n+1}$. As usual, she chose $p(x)$ such that $p(0)=s$. ${\text{Bob}}_1$ through ${\text{Bob}}_{n+1}$ can now gather to jointly discover the secret. However, ${\text{Bob}}_1$ is a malicious adversary and already knows $s$, he wants to sabotage the scheme by making the other parties believe that the secret is in fact some fixed $s^{\prime }\ne s$. How could he achieve this? In other words, what value should he report (in terms variables known in the problem, such as $s^{\prime }$, $s$, or $p(1)$) in order to make the others believe that the secret is $s^{\prime }$?

Solution

The Bobs are using Lagrange interpolation to reconstruct $p(x)$, which is an $n$-degree polynomial satisfying:

$$p(x)=\sum _{i=1}^{n+1}p(1){\lambda }_i(x),$$

where ${\lambda }_i(x)$ are the Lagrange basis polynomials:

$${\lambda }_i(x)=\prod _{j=1}^{n+1}\frac{(x-x_j)}{(x_i-x_j)}.\text{\hspace{1em}(i=j)}$$

Since they are computing $p(0)$, the reconstructed secret is: $p(0)={\sum }_{i=1}^{n+1}p(i){\lambda }_i(0)$. ${\text{Bob}}_1$ wants them to recover $s^{\prime }$, so he must ensure that when they interpolate using his fake share $p^{\prime }(1)$, they obtain $p^{\prime }(0)=s^{\prime }$. The key observation is that only ${\text{Bob}}_1^{\prime }s$ share is incorrect, meaning all other shares remain valid. Let’s express the reconstruction formula where ${\text{Bob}}_1^{\prime }s$ share is tampered:

$$s^{\prime }=p^{\prime }(0)=p(0)+(p^{\prime }(1)-p(1)){\lambda }_1(0).$$

Rearranging for $p^{\prime }(1)$:

$$p^{\prime }(1)=p(1)+\frac{s^{\prime }-s}{{\lambda }_1(0)}.$$

Since ${\lambda }_1(0)={\prod }_{j=2}^{n+1}\frac{-j}{1-j}$, we simplify it to ${\lambda }_1(0)={\prod }_{j=2}^{n+1}\frac{j}{j-1}$, then compute:

$${\lambda }_1(0)=\prod _{j=2}^{n+1}\frac{j}{j-1}=\frac{2}{1}\cdot \frac{3}{2}\cdot \frac{4}{3}\cdots \frac{n+1}{n}=\frac{n+1}{1}=n+1.$$

Thus, $Bo{b}_1$ should report:

$$p^{\prime }(1)=p(1)+\frac{s^{\prime }-s}{n+1}.$$

in order to trick the group into reconstructing $s^{\prime }$ instead of $s$.

Part B

Suppose an oral exam has questions created by $2$ TAs and $3$ readers. The answers are all encrypted, and we know that:

• Two TAs together should be able to access the answers.
• Three Readers together should be able to access the answers.
• One TA and one Reader should also be able to access the answers.
• One TA by themself or two Readers by themselves should not be able to access the answers. Design a secret sharing scheme to make this work.

Solution

Let ${\mathbf{k}}_{TA}$ and ${\mathbf{k}}_R$ be the number of TAs and Readers that must collaborate to access the answers. According to our specification, ${\mathbf{k}}_{TA}=2$, and ${\mathbf{k}}_R=3$. We will use the term threshold here to indicate the minimum number of points needed to interpolate the polynomial; i.e., a degree-$2$ polynomial has a threshold of $3$ (since $3$ points are required to interpolate it). Define three polynomials:

$$\begin{array}{rl}{\mathbf{P}}_{TA}(x)& =a_{1}x+s\\ {\mathbf{P}}_R(x)& =b_2{x}^2+b_{1}x+s\\ {\mathbf{P}}_{TR}(x)& =c_{1}x+s\end{array}$$

Each party is assigned shares as follows:

• Each TA receives:
  • One point $(i,{\mathbf{P}}_{TA}(i))$.
  • One point $(i,{\mathbf{P}}_{TR}(i))$.
• Each Reader receives:
  • One point $(j,{\mathbf{P}}_R(j))$.
  • One point $(j,{\mathbf{P}}_{TR}(j))$.

Two TAs together can interpolate ${\mathbf{P}}_{TA}(x)$, since it is a degree-$1$ polynomial. Three Readers together can interpolate ${\mathbf{P}}_R(x)$, since it is a degree-$2$ polynomial. One TA and one Reader together can interpolate ${\mathbf{P}}_{TR}(x)$, since it is a degree-$1$ polynomial. However, note that this scheme is flawed, since $2$ readers together have access to $2$ points on the degree-$1$ polynomial ${\mathbf{P}}_{TR}(x)$, which is enough to interpolate it and recover $s$, breaking the security of our scheme.