6 files changed, 351 insertions, 0 deletions

diff --git a/Homework/Homework1.pdf b/Homework/Homework1.pdf
new file mode 100644
index 0000000..9a8228a
--- /dev/null
+++ b/Homework/Homework1.pdf
diff --git a/Homework/Homework2.pdf b/Homework/Homework2.pdf
new file mode 100644
index 0000000..1164333
--- /dev/null
+++ b/Homework/Homework2.pdf
diff --git a/Homework/Homework3.ipynb b/Homework/Homework3.ipynb
new file mode 100644
index 0000000..13bad44
--- /dev/null
+++ b/Homework/Homework3.ipynb
@@ -0,0 +1,179 @@
+{
+ "cells": [
+  {
+   "cell_type": "markdown",
+   "metadata": {},
+   "source": [
+    "*For this exercise you should have received this text in .ipynb format. Complete the exercises by modifying this file, and submit the modified version*"
+   ]
+  },
+  {
+   "cell_type": "markdown",
+   "metadata": {},
+   "source": [
+    "**Exercise 1**\n",
+    "\n",
+    "Use SageMath to solve the following problems:\n",
+    "\n",
+    "(a) Find the roots of the following polynomial over $\\mathbb Q$:\n",
+    "\\begin{align*}\n",
+    "    p = 4 x^{7} + 4 x^{6} + 3 x^{5} - 13 x^{4} - 13 x^{3} - 9 x^{2} + 3 x + 3 \\in \\mathbb Q[x]\n",
+    "\\end{align*}\n",
+    "\n",
+    "(b) Find the roots of the same polynomial $p$ over $\\mathbb R$ and over $\\mathbb C$.\n",
+    "\n",
+    "(c) Find the determinant, the trace and the characteristic polynomial of the following matrix:\n",
+    "\\begin{align*}\n",
+    "A=\\left(\\begin{array}{rrrr}\n",
+    "-1 & 1 & -1 & 0 \\\\\n",
+    "1 & \\frac{1}{2} & 1 & 0 \\\\\n",
+    "\\frac{1}{2} & -\\frac{1}{2} & -2 & 1 \\\\\n",
+    "0 & 0 & 1 & 1\n",
+    "\\end{array}\\right)\n",
+    "\\end{align*}\n",
+    "\n",
+    "(d) Find a solution to the linear system $A\\mathbf x =\\mathbf v$, where $A$ is the matrix above and $\\mathbf v=(1, 2, 3, 4)$.\n",
+    "\n",
+    "Write your code in the cell below."
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": null,
+   "metadata": {},
+   "outputs": [],
+   "source": []
+  },
+  {
+   "cell_type": "markdown",
+   "metadata": {},
+   "source": [
+    "**Exercise 2**\n",
+    "\n",
+    "After exchanging messages with the RSA protocol seen in class, Alice and Bob decide to meet and play their favorite game: flip a coin. They like this game very much because it does not take long to set it up and they have exactly the same chances of winning.\n",
+    "\n",
+    "Unfortunately, due to the COVID-19 pandemic they cannot meet in person, and despite being good friends they don't trust each other enough to play this game via Webex call. Luckily, Alice is an expert in cryptography and she knows how to play this game using the Chinese remainder theorem.\n",
+    "\n",
+    "The game plays out as follows:\n",
+    "\n",
+    "(A1) Alice picks two large prime numbers $p$ and $q$, she computes $n=pq$ and sends $n$ to Bob, keeping $p$ and $q$ secret.\n",
+    "\n",
+    "(B1) Bob picks a random number $a$ with $1<a<n$ and $\\gcd(a,n)=1$, computes $b=a^2\\mod n$ and sends $b$ to Alice, keeping $a$ secret.\n",
+    "\n",
+    "(A2) Alice computes two numbers $x$ and $y$ such that $x^2\\equiv b\\pmod p$ and $y^2\\equiv b\\pmod q$ and she uses the Chinese remainder theorem to compute a number $z$ such that $z\\equiv x\\pmod p$ and $z\\equiv y\\pmod q$, so that $z^2\\equiv b\\pmod n$. Then she sends $z$ to Bob.\n",
+    "\n",
+    "Since $n$ is the product of two primes, there are $4$ possible square roots of $b$ modulo $n$, corresponding to the solutions of the four systems of congruences (one for each possible combination of $\\pm$)\n",
+    "\\begin{align*}\\begin{cases}\n",
+    "z\\equiv \\pm x\\pmod p\\\\\n",
+    "z \\equiv \\pm y\\pmod q\n",
+    "\\end{cases}\\end{align*}\n",
+    "\n",
+    "One of those solutions is $a$ and another is $-a$, and Bob knows them. Alice is picking one of the $4$ possible roots at random (she chooses between $x$ and $-x$ and between $y$ and $-y$), so she has $50\\%$ chance of picking one that Bob already knows. This corresponds to Alice flipping a coin, and she wins if she picks $\\pm a$:\n",
+    "\n",
+    "(B2) If $z\\equiv\\pm a\\pmod n$, Bob declares to have lost. Otherwise, Bob claims to have won, and as proof he produces one prime factor of $n$ by computing $g=\\gcd(n,a+z)$. *(One can prove that in this situation $g$ is always one of the two prime factors of $n$.)*\n",
+    "\n",
+    "Since factoring a number without extra information is very hard, Alice will be convinced that she must have given Bob one of the square roots that he did not know, so she admits the loss.\n",
+    "\n",
+    "Now to the actual exercise:\n",
+    "\n",
+    "(a) Write the code for the functions A1, B1 and B2 as indicated in the cell below. The function A2 is already written.\n",
+    "\n",
+    "(b) Modify the functions B1, A2 and B2 to check that the opponent is not cheating. More precisely:\n",
+    "* In B1, Bob should check that $n$ is not a prime power. *(This is the only way Alice can try to cheat: if she sends Bob a number $n$ that is the product of more than two primes, than she has less than $50\\%$ chance of winning!)*\n",
+    "* In A2, Alice should check that $b$ is a square modulo $n$.\n",
+    "* In B2, Bob should check that $z^2\\equiv a^2\\pmod n$.\n",
+    "\n",
+    "In case cheating is detected, a message should be printed saying that the person is cheating."
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 1,
+   "metadata": {
+    "collapsed": true
+   },
+   "outputs": [
+    {
+     "ename": "IndentationError",
+     "evalue": "expected an indented block (<ipython-input-1-60f510bf175f>, line 7)",
+     "output_type": "error",
+     "traceback": [
+      "\u001b[1;36m  File \u001b[1;32m\"<ipython-input-1-60f510bf175f>\"\u001b[1;36m, line \u001b[1;32m7\u001b[0m\n\u001b[1;33m    def B1(n):\u001b[0m\n\u001b[1;37m    ^\u001b[0m\n\u001b[1;31mIndentationError\u001b[0m\u001b[1;31m:\u001b[0m expected an indented block\n"
+     ]
+    }
+   ],
+   "source": [
+    "# Alice needs this to compute the square roots\n",
+    "from sage.rings.finite_rings.integer_mod import square_root_mod_prime\n",
+    "\n",
+    "def A1():\n",
+    "    # This function must return two distinct primes and their product.\n",
+    "    \n",
+    "def B1(n):\n",
+    "    # This function must return a random integer a\n",
+    "    # with 1<a<n and gcd(a,n)=1.\n",
+    "\n",
+    "def A2(b, p, q):\n",
+    "    x = ZZ(square_root_mod_prime(Integers(p)(b), p))\n",
+    "    y = ZZ(square_root_mod_prime(Integers(q)(b), q))\n",
+    "    return crt(x, y, p, q)\n",
+    "\n",
+    "def B2(a, z, n):\n",
+    "    # This function must print out one of two messages:\n",
+    "    # \"Bob has lost\" if z is congruent to a or -a modulo n.\n",
+    "    # \"Bob has won, proof: \" followed by a prime factor of n otherwise.\n",
+    "    # In this case the prime must be calculated as explained above.\n",
+    "\n",
+    "\n",
+    "# This is how the game plays out:\n",
+    "p, q, n = A1()\n",
+    "print(\"Alice picked n =\", n)\n",
+    "print(\"[[ Alice's secret:\", p, q, \"]]\")\n",
+    "a = B1(n)\n",
+    "b = a^2 % n\n",
+    "print(\"Bob picked b =\", b)\n",
+    "print(\"[[ Bob's secret:\", a, \"]]\")\n",
+    "z = A2(b, p, q)\n",
+    "print(\"Alice picked z =\", z)\n",
+    "B2(a, z, n)"
+   ]
+  },
+  {
+   "cell_type": "markdown",
+   "metadata": {},
+   "source": [
+    "**Grading**\n",
+    "\n",
+    "This homework assignment is worth $20\\%$ of your final grade. Exercise 1 is worth 4 points (one for each part) and Exercise 2 is worth 12 points (8 points for part (a) and 4 points for part (b)), for a total of **16 points**."
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": null,
+   "metadata": {},
+   "outputs": [],
+   "source": []
+  }
+ ],
+ "metadata": {
+  "kernelspec": {
+   "display_name": "SageMath 9.2",
+   "language": "sage",
+   "name": "sagemath"
+  },
+  "language_info": {
+   "codemirror_mode": {
+    "name": "ipython",
+    "version": 3
+   },
+   "file_extension": ".py",
+   "mimetype": "text/x-python",
+   "name": "python",
+   "nbconvert_exporter": "python",
+   "pygments_lexer": "ipython3",
+   "version": "3.8.5"
+  }
+ },
+ "nbformat": 4,
+ "nbformat_minor": 4
+}
diff --git a/Homework/Homework3.pdf b/Homework/Homework3.pdf
new file mode 100644
index 0000000..13d55cf
--- /dev/null
+++ b/Homework/Homework3.pdf
diff --git a/Homework/Homework4.ipynb b/Homework/Homework4.ipynb
new file mode 100644
index 0000000..99481b9
--- /dev/null
+++ b/Homework/Homework4.ipynb
@@ -0,0 +1,172 @@
+{
+ "cells": [
+  {
+   "cell_type": "markdown",
+   "metadata": {},
+   "source": [
+    "*For this exercise you should have received this text in .ipynb format. Complete the exercises by modifying this file, and submit the modified version*\n",
+    "\n",
+    "**Deadline:** Sunday, June 6."
+   ]
+  },
+  {
+   "cell_type": "markdown",
+   "metadata": {},
+   "source": [
+    "**Exercise 1 (6 points)**\n",
+    "\n",
+    "Use Sage to find the intersection points *in the real plane* (that is, only those points such that *both* coordinates are real numbers) of the following pairs of geometric objects:\n",
+    "\n",
+    "* The circle of equation $x^2 + y^2 = 4$ and the ellipse of equation $\\left(\\frac x2\\right)^2 + (2y)^2 = 4$.\n",
+    "* The circle of equation $x^2 + y^2 = 4$ and the ellipse of equation $\\left(\\frac x2-2\\right)^2 + (2y)^2 = 4$.\n",
+    "* The curve of equation $y^2 = x^3 -x +1$ and the horizontal line $y=10$.\n",
+    "* The $x$-axis and the graph of the function $f(x)=\\log(x) - e^{-x}$. *Hint: $f(x)$ has only one real zero.*"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": null,
+   "metadata": {},
+   "outputs": [],
+   "source": []
+  },
+  {
+   "cell_type": "markdown",
+   "metadata": {},
+   "source": [
+    "**Exercise 2 (6 points)**\n",
+    "\n",
+    "(a) Use Sage to compute\n",
+    "* the derivative\n",
+    "* a primite (i.e. integral)\n",
+    "* the power series expansion around $0$ up to order $4$\n",
+    "\n",
+    "of the following functions:\n",
+    "* $f(x) = e^x$\n",
+    "* $f(x) = \\sin(x)$\n",
+    "* $f(x) = \\cos(x)$\n",
+    "* $f(x) = \\tan(x)$\n",
+    "* $f(x) = \\log(1+x)$\n",
+    "* $f(x) = \\sqrt[3]{1+x}$\n",
+    "\n",
+    "(b) Use Sage to get the Latex code that represents the objects you computed above.\n",
+    "\n",
+    "(c) Arrange the results of the previous points in a table in Latex. The table should have 4 columns (function, derivative, integral, series) and one row for each of the functions above. *Note: when including Latex in a Markdown cell in Jupyter you will not receive any warning if you make mistakes; instead the Latex will simply not be rendered and it will appear as plain text. If you have troubles making this work you can send me a separate .tex (and .pdf) file.*"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": null,
+   "metadata": {},
+   "outputs": [],
+   "source": [
+    "# Compute derivatives etc..."
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": null,
+   "metadata": {},
+   "outputs": [],
+   "source": [
+    "# Compute Latex code"
+   ]
+  },
+  {
+   "cell_type": "markdown",
+   "metadata": {},
+   "source": [
+    "(Write your table here)"
+   ]
+  },
+  {
+   "cell_type": "markdown",
+   "metadata": {},
+   "source": [
+    "**Exercise 3 (4 points)**\n",
+    "\n",
+    "The equation\n",
+    "\\begin{align*}\n",
+    "y^2+x^{16}=1\n",
+    "\\end{align*}\n",
+    "determines a closed curve in $\\mathbb R^2$ that looks like a rounded square. Determine the area of that shape, giving both an exact value (which might depend on some functions that Sage knows, but you don't) and an approximate value."
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": null,
+   "metadata": {},
+   "outputs": [],
+   "source": []
+  },
+  {
+   "cell_type": "markdown",
+   "metadata": {},
+   "source": [
+    "**Exercise 4 (12 points)**\n",
+    "\n",
+    "A team of biologists is monitoring the population of river shrimps in the Alzette. At first they thought that the size $P(t)$ of their population on day $t$ would satisfy the differential equation $P'(t)=P(t)/10$. However this does not work well with the data they have collected, so they now believe that the population of shrimps follows the formula $P'(t)=P(t)/10-b$ for some value of $b$ between 1 and 100. They need your help here.\n",
+    "\n",
+    "(a) Using Sage, find a solution for the differential equation with initial conditions\n",
+    "\\begin{align*}\n",
+    "\\begin{cases}\n",
+    "P'(t)&=\\frac{P(t)}{10}-b\\\\\n",
+    "P(1)&=1000\n",
+    "\\end{cases}\n",
+    "\\end{align*}\n",
+    "where $b$ is a generic constant.\n",
+    "\n",
+    "(b) The list `data` in the cell below contains the actual number of shrimps that was measured every day from day $1$ (the $0$ at the beginning is meaningless, but it will help to keep it there). Plot in one single picture, possibly using different colors for each:\n",
+    "* The data as a bar chart.\n",
+    "* A curve that interpolates the data, using one of the methods shown in class.\n",
+    "* The solution of the differential equation for $b=0$.\n",
+    "* The solution of the differential equation for a value of $b$ of your choice ($1\\leq b\\leq 100$) that fits the data better than $b=0$. *(For this last point there is no right or wrong choice, just pick one that looks good)*"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": null,
+   "metadata": {},
+   "outputs": [],
+   "source": [
+    "data = [0, 1000, 1123, 1223, 1190, 1432, 1553, 1709, 1826, 1980, 2146, 2172, 2383, 2588, 2822, 3401, 3330, 4157, 3994, 4995, 5392, 5910, 6468, 7128, 7325, 7984, 9634, 10473, 11761, 12777]\n"
+   ]
+  },
+  {
+   "cell_type": "markdown",
+   "metadata": {},
+   "source": [
+    "**Grading**\n",
+    "\n",
+    "This homework assignment is worth $28$ ($24+4$) points, distributed as described above.\n",
+    "\n",
+    "Your final grade for the course will be the total of points you obtained (notice that the maximum is $20+20+16+28=84$) divided by $4$, rounded to the nearest integer. More precisely\n",
+    "\n",
+    "\\begin{align*}\n",
+    "\\operatorname{grade} = \\operatorname{min}\\left(20, \\left\\lfloor \\frac{\\operatorname{total}}{4} + 0.5\\right\\rfloor\\right)\n",
+    "\\end{align*}"
+   ]
+  }
+ ],
+ "metadata": {
+  "kernelspec": {
+   "display_name": "SageMath 9.0",
+   "language": "sage",
+   "name": "sagemath"
+  },
+  "language_info": {
+   "codemirror_mode": {
+    "name": "ipython",
+    "version": 3
+   },
+   "file_extension": ".py",
+   "mimetype": "text/x-python",
+   "name": "python",
+   "nbconvert_exporter": "python",
+   "pygments_lexer": "ipython3",
+   "version": "3.8.5"
+  }
+ },
+ "nbformat": 4,
+ "nbformat_minor": 4
+}
diff --git a/Homework/Homework4.pdf b/Homework/Homework4.pdf
new file mode 100644
index 0000000..ff8ecd2
--- /dev/null
+++ b/Homework/Homework4.pdf