mathsoftware

Homework3-checkpoint.ipynb (7576B)

---

 {
  "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
 }