mathsoftware

solution-checkpoint.ipynb (6547B)

---

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