\dbox{{\bf Deliverable:} Submit your responses as a single, readable PDF file on the collab site before {\bf 6:29pm} on {\bf Friday, 1 December}.}

Directions

Solve all the 9 problems. Your answers should be clear, consise, and convincing.

Wily Theorem

1. Fermat’s last theorem, proved by Andrew Wiles in 1994, states that: for any natural $n>2$ there are \emph{no} natural numbers $a,b,c$ such that $$ a^n + b^n = c^n.$$ Assuming Fermat’s theorem, give a simple proof that $\sqrt[n]{2}$ is \emph{not} a rational number.

   (Hint: you can also give a dirct proof that does not use the Fermat’s last theorem, but note that you then might loose the joy of proving a corollary to Fermat’s theorem :)

Fast Exponentiation

1. In the Diffie Hellman key-exchange protocol described in Class 23, Alice and Bob need to compute $g^x \mod p$ and $g^y \mod p$ for some $1 \leq g,x,y \leq p-1$. Suppose $p$ is a (prime) number that has 1000 bits when represented in binary.

   (a) Explain what is wrong (from a practical efficiency point of view) with using the following algorithm for computing $g^x$. (The $rem(a,p)$ operation computes the remainder of $a$ modulo $p$ using the well-known efficient division algorithm.)

   def SlowExp(g,p,x):
           a = 1 
           while x > 0:
               a = a * g
               a = rem(a,p)
               x = x - 1
           return a
   

   Hint: try to estimate how many multiplications are used.

   (b) Describe a modified version of the “Fast Exponentiation Program” in Section 6.3.1 of the book that is useful computing $g^x \mod p$. How many multiplications does this program do in maximum to obtain $g^x$ for an arbitrary $1\leq x\leq p-1$ for a 1000 digit $p$?

Abelian Groups

For each set ($R$) and operator ($P$) described below, explain why it is not an Abelian group (defined in Class 22). Your answer should include a convincing supporting argument that shows why the given set and operator do not satisfy at least one of the required properties.

1. $R = \mathbb{Z}, P = \text{\em gcd}$ where $\text{\em gcd}$ is a binary operator that takes two integers as input and outputs their greatest common divisor.

2. $R = \mathbb{Z}, P = -$.

3. $R = {T, F}, P = \text{OR}$. (Hint: what must the identity be, and which element has no inverse?)

Fields

For each set ($R$) and first and second operations ($P+$, $P\times$), answer if the set and operations are a field (as defined in Class 23). A good answer will either show how the given set and operations satisfy the required properties (including explaning what the additive identify and multiplicative identity are), or show how it fails to satisfy one of the required properties.

1. $R = \mathbb{N}{12}, P+ = +\; (\text{mod}\, 12), P_\times = \times\; (\text{mod}\, 12)$.

2. $R = { \sharp, \flat }$ $P+ = { (\sharp, \sharp) \rightarrow \sharp, (\sharp, \flat) \rightarrow \flat, (\flat, \sharp) \rightarrow \flat, (\flat, \flat) \rightarrow \sharp }$ and $P\times = { (\sharp, \sharp) \rightarrow \sharp, (\sharp, \flat) \rightarrow \sharp, (\flat, \sharp) \rightarrow \sharp, (\flat, \flat) \rightarrow \flat }.$

3. $R = \mathbb{N}{31}, P+ = \times\; (\text{mod}\, 31), P_\times = +\; (\text{mod}\, 31)$.

Field Properties

1. ($\star$) Suppose $R$ is an arbitrary field with some additive and multiplicative operations $P+, P\times$. Suppose we are given any $a,b,c\in R$ where $a \neq 0$; namely, $a$ is not the additive identity element (usually denoted with $0$). Then prove that there is a unique solution for variable $x \in R$ that satisfies $(a ~P\times~ x) ~P+~ b = c$.

   Hint: use the properties of the fields and describe a step by step process to actually find $x$.

   (Note the interesting message of this problem: fields shape the abstract notion that allows solving linear equations. Here we show it for a single variable linear equation, but the idea actually extends to multi-variable systems of equations.)