From d6c61d988bfa4255baf9cdae42db59ebee38363f Mon Sep 17 00:00:00 2001
From: Sebastiano Tronto <sebastiano.tronto@gmail.com>
Date: Tue, 25 May 2021 17:10:49 +0200
Subject: Added files

---
 .../.ipynb_checkpoints/Homework3-checkpoint.ipynb  | 179 +++++++++++++++++++++
 .../.ipynb_checkpoints/solution-checkpoint.ipynb   | 166 +++++++++++++++++++
 2 files changed, 345 insertions(+)
 create mode 100644 src/Homework3/.ipynb_checkpoints/Homework3-checkpoint.ipynb
 create mode 100644 src/Homework3/.ipynb_checkpoints/solution-checkpoint.ipynb

(limited to 'src/Homework3/.ipynb_checkpoints')

diff --git a/src/Homework3/.ipynb_checkpoints/Homework3-checkpoint.ipynb b/src/Homework3/.ipynb_checkpoints/Homework3-checkpoint.ipynb
new file mode 100644
index 0000000..13bad44
--- /dev/null
+++ b/src/Homework3/.ipynb_checkpoints/Homework3-checkpoint.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/src/Homework3/.ipynb_checkpoints/solution-checkpoint.ipynb b/src/Homework3/.ipynb_checkpoints/solution-checkpoint.ipynb
new file mode 100644
index 0000000..41ee2ea
--- /dev/null
+++ b/src/Homework3/.ipynb_checkpoints/solution-checkpoint.ipynb
@@ -0,0 +1,166 @@
+{
+ "cells": [
+  {
+   "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",
+    "*(Yes, I know that the exercise is long to read, but it will not be so long to solve. It is a cool application of cryptography which, similarly to RSA, is based on the fact that factoring a number is hard.)*\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 much time 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 they despite being good friends they don't trust each other enough to play this game via videocall. 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 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$. 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. Since 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. She will win 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"
+   ]
+  },
+  {
+   "cell_type": "code",
+   "execution_count": 12,
+   "metadata": {},
+   "outputs": [
+    {
+     "name": "stdout",
+     "output_type": "stream",
+     "text": [
+      "Alice picked n = 239880868500983\n",
+      "(Alice's secret: 15489269 15486907 )\n",
+      "Bob picked b = 19945704365802\n",
+      "(Bob's secret: 3040890259756 )\n",
+      "Alice picked z = 3040890259756\n",
+      "Bob has lost\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",
+    "    p, q = 0, 0\n",
+    "    while p == q:\n",
+    "        p = Primes()[10^6+randint(1,1000)]\n",
+    "        q = Primes()[10^6+randint(1,1000)]\n",
+    "    return p, q, p*q\n",
+    "    \n",
+    "def B1(n):\n",
+    "    a = 0\n",
+    "    while gcd(a,n) != 1:\n",
+    "        a = randint(2,n-1)\n",
+    "    return a\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",
+    "    if a%n == z%n or a%n == (-z)%n:\n",
+    "        print(\"Bob has lost\")\n",
+    "    else:\n",
+    "        print(\"Bob has won, proof:\", gcd(n, a+z))\n",
+    "\n",
+    "# This is how the game plays:\n",
+    "p, q, n = A1()  # p and q are secret to Alice\n",
+    "print(\"Alice picked n =\", n)\n",
+    "print(\"(Alice's secret:\", p, q, \")\")\n",
+    "a = B1(n)       # a is secret to Bob\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": "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
+}
-- 
cgit v1.3