Práctica 8 - Factorización en DE2 .ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Factorización en anillos de enteros de cuerpos cuadráticos $\\mathbb{Q}(\\sqrt{d})$, con $d>0$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Vamos a estudiar como factorizar en los anillos de enteros $\\mathbb{O}$ de cuerpos cuadráticos $\\mathbb{Q}(\\sqrt{d})$ con $d>0$, en el caso en que $\\mathbb O$ sea un D.E. Recordar que esto ocurre cuando \n",
    "$$\n",
    "d=2,3,5,6,7,11,13,17,19,21,29,33,37,41,57,73.\n",
    "$$\n",
    "\n",
    "Para poder llevar una notación homogénea vamos a denotar \n",
    "$$ \n",
    "e = \\sqrt d \\quad\\mbox{si}\\quad d\\not\\equiv 1\\mod 4 \\quad  \\mbox{y} \\\\  \\quad e = \\frac{1+\\sqrt d}{2} \\quad \\quad\\mbox{si}\\quad d\\equiv 1\\mod 4\n",
    "$$\n",
    "\n",
    "Un elemento de $\\mathbb{O}$ será una expresión de la forma $\\alpha=a+b*e$, con $a,b\\in \\mathbb{Z}$. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "El algoritmo de factorización es estos anillos es básicamente el mismo que para el caso $d<0$. La diferencia estriba principalmente en el cálculo de los elementos con una determinada norma.\n",
    "\n",
    "El primer problema que tenemos que resolver es el cálculo de conjugados ya que, en este caso, el conjugado de un elemento de $\\mathbb Q(\\sqrt d )$ no es el conjugado complejo."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from sympy import *"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "from TANMLP import *"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "12"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "norma(2+2*sqrt(-2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(2, 0)"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ab(2,-3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Por tanto tomamos:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "e1=(1+sqrt(29))/2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1/2 + sqrt(29)/2"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "e1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Intoducimos algunos elementos del anillo de enteros"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [],
   "source": [
    "alpha= simplify(2-17*e1);\n",
    "beta= simplify(5-6*e1)\n",
    "alpha1=Rational(1,2)+Rational(3,2)*sqrt(29)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(-17*sqrt(29)/2 - 13/2, -3*sqrt(29) + 2, 1/2 + 3*sqrt(29)/2, 4*sqrt(29) + 727)"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(alpha, beta, alpha1, simplify(alpha*beta+alpha1))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Vemos que hace la función conjugate"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "-17*sqrt(29)/2 - 13/2"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "alpha.conjugate()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Por tanto $\\alpha .conjugate()=\\alpha$ y no nos vale."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## La función <span style=\"color:red\">xy($\\alpha$,d)</span>."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Cualquier elemento $\\alpha\\in \\mathbb Q(\\sqrt d)$ se escribe como $\\alpha=x+y*\\sqrt d$ con $x,y \\in \\mathbb Q$, pero no podemos utilizar el conjugado para recuperara $x$ e $y$. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### La función <span style=\"color:red\">args</span>.\n",
    "\n",
    "Para definir la función <span style=\"color:red\">xy($\\alpha$,d)</span> podemos utilizar la función <span style=\"color:red\">args</span>, pero hay que utilizarla con cuidado, pongo algunos ejemplos:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "a1=2\n",
    "a2=Rational(1,2)\n",
    "a3=sqrt(29)\n",
    "a4=3*sqrt(29)\n",
    "a5=Rational(1,2)*sqrt(29)\n",
    "a6=Rational(3,2)\n",
    "a7=Rational(5,2)*sqrt(29)\n",
    "a8=Rational(3,2)+Rational(5,2)*sqrt(29)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(3/2, 5*sqrt(29)/2)"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a8.args"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(5/2, sqrt(29))"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a7.args"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "()"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a6.args"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(1/2, sqrt(29))"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a5.args"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(3, sqrt(29))"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a4.args"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(29, 1/2)"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a3.args"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "()"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a2.args"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    "#a1.args"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2\n"
     ]
    }
   ],
   "source": [
    "sa1=simplify(a1)\n",
    "print sa1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sa1.coeff(sqrt(29),0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sa1.coeff(sqrt(29),1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Ejercicio 1.-** Redefine la función <span style=\"color:red\">xy($\\alpha$,d)</span>, de la tarea anterior, para que valga tanto para $d<0$ como para $d>0$. \n",
    "\n",
    "Para definir esta función <span style=\"color:red\">xy($\\alpha$,d)</span> puedes usar la funcione <span style=\"color:red\">args</span> o cualquier otra función de Python que encuentres. Pero, asegúrate de que <span style=\"color:red\">xy($\\alpha$,d)</span> hace lo que debe en los distintos casos que se pueden dar. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [],
   "source": [
    "def xy2(alpha,d):\n",
    "    #Calculamos las coordenadas racionales de alpha\n",
    "    if d!=0:\n",
    "        alpha2=simplify(alpha)\n",
    "        x=alpha2.coeff(sqrt(d),0)\n",
    "        y=alpha2.coeff(sqrt(d),1)\n",
    "        return (x,y)\n",
    "    else:\n",
    "        print \"Mete un d distinto de cero\"\n",
    "        return false"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## El resto de las funciones auxiliares"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Ejercicio 2.-** Redefine las siguientes funciones de la tarea factDE1 para que funcionen tanto para $d<0$ como para $d>0$:\n",
    "\n",
    "- <span style=\"color:red\">norma($\\alpha$,d)</span>, \n",
    "- <span style=\"color:red\">traza($\\alpha$,d)</span>,\n",
    "- <span style=\"color:red\">es_entero($\\alpha$,d)</span>,\n",
    "- <span style=\"color:red\">ab($\\alpha$,d)</span>, \n",
    "- <span style=\"color:red\">divide($\\alpha,\\beta$,d)</span>,\n",
    "- <span style=\"color:red\">cociente($\\alpha,\\beta$,d)</span> y\n",
    "- <span style=\"color:red\">es_unidad($\\alpha$,d)</span>."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Como tengo todas estas funciones en mi TANMLP, vamos a llamar a estas funciones con otro nombre para que no haya confusión y sobreescribamos funciones.\n",
    "Le pondremos un 2 después del nombre para diferenciar que ésta es de la práctica de factorización en DE2 y que funcionan\n",
    "tanto para esta práctica como para la antigua."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [],
   "source": [
    "def norma2(alpha,d):\n",
    "    #Calculamos la norma de alpha sea cual sea el d\n",
    "    if d!=0:\n",
    "        coord=xy2(alpha,d)\n",
    "        conj=coord[0]-coord[1]*sqrt(d)\n",
    "        norma=expand(simplify(alpha*conj))\n",
    "        return norma\n",
    "    else:\n",
    "        print \"Mete un d distinto de cero\"\n",
    "        return false    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [],
   "source": [
    "def traza2(alpha,d):\n",
    "    #Calculamos la traza de alpha sea cual sea el d\n",
    "    if d!=0:\n",
    "        coord=xy2(alpha,d)\n",
    "        conj=expand(simplify(coord[0]-coord[1]*sqrt(d)))\n",
    "        traza=expand(simplify(alpha+conj))\n",
    "        return traza\n",
    "    else:\n",
    "        print \"Mete un d distinto de cero\"\n",
    "        return false "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def es_entero2(alpha,d):\n",
    "    #Comprobamos si el elemento alpha es entero algebraico o no\n",
    "    norm=norma2(alpha,d)\n",
    "    traz=traza2(alpha,d)\n",
    "    #Comprobamos si la norma y la traza son enteras \n",
    "    return ask(Q.integer(traz))and ask(Q.integer(norm))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "scrolled": true
   },
   "outputs": [],
   "source": [
    "def ab2(alpha,d):\n",
    "    #Si alpha es entero, calculamos sus coordenadas enteras\n",
    "    if es_entero2(alpha,d)==true:\n",
    "        if d<0:\n",
    "            if d==-1 or d==-2:\n",
    "                e=sqrt(d)\n",
    "                a=(alpha+alpha.conjugate())/2\n",
    "                b=(alpha-alpha.conjugate())/(2*sqrt(d))\n",
    "            elif d==-3 or d==-7 or d==-11:\n",
    "                e=Rational(1,2)+sqrt(d)*Rational(1,2)\n",
    "                coord=xy2(alpha,d)\n",
    "                x_1=coord[0]*2\n",
    "                y_1=coord[1]*2\n",
    "                a=(x_1-y_1)/2\n",
    "                b=y_1\n",
    "            else:\n",
    "                return \"Introduzca un dominio euclideo\"\n",
    "            return(a,b)\n",
    "        elif d>0:\n",
    "            if d%4==1:\n",
    "                e=Rational(1,2)+sqrt(d)*Rational(1,2)\n",
    "                coord=xy2(alpha,d)\n",
    "                x_1=coord[0]*2\n",
    "                y_1=coord[1]*2\n",
    "                a=(x_1-y_1)/2\n",
    "                b=y_1\n",
    "                \n",
    "            else:\n",
    "                e=sqrt(d)\n",
    "                coord=xy2(alpha,d)\n",
    "                conj=coord[0]-coord[1]*sqrt(d)\n",
    "                a=(alpha+conj)/2\n",
    "                b=(alpha-conj)/(2*sqrt(d))\n",
    "            return(a,b)\n",
    "        else:\n",
    "            print \"Introduce un d distinto de 0\"\n",
    "            return false\n",
    "    else:\n",
    "        return \"Introduzca un entero algebraico\"\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [],
   "source": [
    "def divide2(alpha,beta,d):\n",
    "    #Comprobamos si alpha divide a beta, para ello vemos multiplicando por el conjugado si la fracción es un entero\n",
    "    coord_alpha=xy2(alpha,d)\n",
    "    conj=coord_alpha[0]-coord_alpha[1]*sqrt(d)\n",
    "    num=expand(simplify(beta*conj))\n",
    "    norm=norma2(alpha,d)\n",
    "    coord_num=xy2(num,d)\n",
    "    division=Rational(coord_num[0],norm)+Rational(coord_num[1],norm)*sqrt(d)\n",
    "    return es_entero2(division,d)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [],
   "source": [
    "def cociente2(alpha,beta,d):\n",
    "    #Si alpha divide a beta calculamos su cociente\n",
    "    if divide2(alpha,beta,d)!=true:\n",
    "        return false\n",
    "    coord_alpha=xy2(alpha,d)\n",
    "    conj=coord_alpha[0]-coord_alpha[1]*sqrt(d)\n",
    "    division=expand(simplify((beta*conj)/norma2(alpha,d)))\n",
    "    return division"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [],
   "source": [
    "def es_unidad2(alpha,d):\n",
    "    #Vemos si alpha es una unidad\n",
    "    return abs(norma2(alpha,d))==1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# La ecuación de Pell general $$x^2-d*y^2=n.$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Cuando $d>0$ esta ecuación tiene infinitas soluciones o ninguna.\n",
    "\n",
    "El método de resolución que aquí presentamos está basado en el articulo de J.P. Robertson ***\"Solving the general Pell equation $x^2-Dy^2=N$\".*** Que podéis encontrar en http://www.jpr2718.org/pell.pdf.\n",
    "\n",
    "Recordar que $d$ debe ser un entero positivo libre de cuadrados. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Ejercicio 3.-** Define una función <span style=\"color:red\">libre_de_cuadrados(d)</span> con salida true o false según $d$ sea o no libre de cuadrados. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def libre_de_cuadrados(d):\n",
    "    #Vemos si d es libre de cuadrados, para ello hacemos una lista de sus factores\n",
    "    #Y vemos si es divisible por alguno de ellos al cuadrado\n",
    "    d1=abs(d)\n",
    "    lista=list(factorint(d1))\n",
    "    for i in range(0,len(lista)):\n",
    "        if d1%(lista[i]**2)==0:\n",
    "            return false\n",
    "    return true"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## La ecuación de Pell  $$x^2-d*y^2=1.$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Para resolver la ecuación general de Pell primero deberemos resolverla para el caso $n=1$.\n",
    "\n",
    "Procedemos de la siguiente forma:\n",
    "\n",
    "- Calculamos la fracción continua asociada a $\\sqrt d$, \n",
    "<center> F = <span style=\"color:green\"> continued_fraction_periodic </span>(0,1,d)=$[a_0,[a_1,\\ldots,a_r]]$.</center>\n",
    "- Definimos la lista $$L=[a_0,a_1,\\ldots,a_{r-1}].$$\n",
    "**Notar que:** $a_r=2*a_0$.\n",
    "- Calculamos los <span style=\"color:green\">convergentes continued_fraction_convergents</span>(L).\n",
    "- Tomamos $x_0$ e $y_0$ el numerador y el denominador, respectivamente, del último convergente.\n",
    "- Entonces $(x_0,y_0)$ es una solución de:\n",
    "$$                \n",
    "x_0^2-d*y_0^2 =  1  \\quad \\mbox{si len(L) es par} \\\\\n",
    "x_0^2-d*y_0^2 = -1  \\quad \\mbox{si len(L) es impar}.\n",
    "$$\n",
    "\n",
    "**NOTAR QUE:** Si $u=x_0+y_0*\\sqrt d$ tiene norma -1 entonces $u^2$ tiene norma 1. \n",
    "\n",
    "Esto nos permite encontrar siempre una solución de la ecuación $x^2-d*y^2=1$, aunque len(L) sea impar. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "**Ejercicio 4.-** Define una función <span style=\"color:red\">pell(d)</span> para resolver la ecuación de Pell anterior."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [],
   "source": [
    "def pell(d):\n",
    "    #Resolvemos la ecuación de Pell anterior\n",
    "    if libre_de_cuadrados(d)==false:\n",
    "        print \"introduce un número libre de cuadrados\"\n",
    "        return false\n",
    "    if d<=1 or type(d)!=int:\n",
    "        print \"Introduce un d entero positivo válido\"\n",
    "        return false\n",
    "    #Calculamos la fracción continua periódica\n",
    "    F = continued_fraction_periodic (0,1,d)\n",
    "    L= [F[0]]+F[1]\n",
    "    #Quitamos el ultimos elemento\n",
    "    L.pop()\n",
    "    #Calculamos la lista de convergentes\n",
    "    convergentes=list(continued_fraction_convergents(L))\n",
    "    \n",
    "    #Damos la solución de la ecuación\n",
    "    if len(L)%2==0:\n",
    "        x=fraction(convergentes[len(convergentes)-1])[0]\n",
    "        y=fraction(convergentes[len(convergentes)-1])[1]\n",
    "        return (x,y)\n",
    "    else:\n",
    "        x=fraction(convergentes[len(convergentes)-1])[0]\n",
    "        y=fraction(convergentes[len(convergentes)-1])[1]\n",
    "        u=x+y*sqrt(d)\n",
    "        u_2=expand(u**2)\n",
    "        coord_u2=xy2(u_2,d)\n",
    "        return coord_u2\n",
    "        \n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## La ecuación de Pell general $$x^2-d*y^2=n.$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La ecuación general de Pell $x^2- d*y^2 = n$ tiene infinitas o ninguna solución. \n",
    "\n",
    "Si esta ecuación tiene solución hay unas pocas que generan todas las demás, \n",
    "estas son llamadas **soluciones generadoras** (ver el artículo de Robertson).\n",
    "\n",
    "Para resolver la ecuación $x^2-d*y^2=n$ (con $d$ libre de cuadrados) procedemos de la siguiente forma:\n",
    "\n",
    " - Calculamos una solución de la ecuación $x^2-d*y^2=1$. Supongamos esta $(r,s)$ ($r$ y $s$ positivos).\n",
    " - Calculamos las cotas para $y$. \n",
    " \n",
    " Estas serán:\n",
    "            \n",
    "  - Si $n>0,\\quad 0\\leq y \\leq \\sqrt{\\frac{n*(r-1)}{2d}}$.\n",
    "  \n",
    "  - Si $n<0, \\quad\\sqrt{\\frac{-n}{d}}\\leq y \\leq \\sqrt{\\frac{-n*(r+1)}{2d}}$.\n",
    "\n",
    " - Para $y$ entre las cotas, formamos la lista de aquellos $x^2=d*y^2+n$ que son un cuadrado. Si ninguno de estos elementos es un cuadrado, la ecuación no tienen solución. En otro caso:\n",
    " - Las soluciones generadoras serán $(±x,y)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "**Ejercicio 5.-** Define una función <span style=\"color:red\">generalpell(d,n)</span> para resolver la ecuación general de Pell. Pon varios ejemplos, algunos en los que se tenga solución y otros no, y comprueba los resultados."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [],
   "source": [
    "def generalpell(n,d):\n",
    "    #Resolvemos la ecuación general de Pell\n",
    "    if libre_de_cuadrados(d)==false:\n",
    "        print \"introduce un número libre de cuadrados\"\n",
    "        return false\n",
    "        \n",
    "    if d>1:\n",
    "        #Resolvemos la ecuación de Pell anterior\n",
    "        sol_pell=pell(d)\n",
    "        r=abs(sol_pell[0])\n",
    "        s=abs(sol_pell[1])\n",
    "        sol=[]\n",
    "        if n==1:\n",
    "            #Si n es 1, añadimos la solución de pell\n",
    "            (s1,s2)=sol_pell\n",
    "            if s1==0:\n",
    "                sol.append((s1,s2))\n",
    "                sol.append((s1,-s2))\n",
    "            elif s2==0:\n",
    "                sol.append((s1,s2))\n",
    "                sol.append((-s1,s2))\n",
    "            else:\n",
    "                sol.append((s1,s2))\n",
    "                sol.append((-s1,s2))\n",
    "                sol.append((s1,-s2))\n",
    "                sol.append((-s1,-s2))\n",
    "        if n>0:\n",
    "            #Calculamos la cota\n",
    "            ymax=sqrt((n*(r-1))/(2*d))\n",
    "            for y in range(0,ymax+1):\n",
    "                x=n+d*(y**2)\n",
    "                x=sqrt(x)\n",
    "                if ask(Q.integer(x)):\n",
    "                    if x==0:\n",
    "                        sol.append((x,y))\n",
    "                        sol.append((x,-y))\n",
    "                    elif y==0:\n",
    "                        sol.append((x,y))\n",
    "                        sol.append((-x,y))\n",
    "                    else:\n",
    "                        sol.append((x,y))\n",
    "                        sol.append((-x,y))\n",
    "                        sol.append((x,-y))\n",
    "                        sol.append((-x,-y))\n",
    "            return sol\n",
    "        elif n<0:\n",
    "            #Calculamos las cotas\n",
    "            ymin=sqrt(-n/d)\n",
    "            ymax=sqrt((-n*(r+1))/(2*d))\n",
    "            for y in range(ymin,ymax+1):\n",
    "                x=n+d*(y**2)\n",
    "                x=sqrt(x)\n",
    "                #Vemos si x es un cuadrado\n",
    "                if ask(Q.integer(x)):\n",
    "                    if x==0:\n",
    "                        sol.append((x,y))\n",
    "                        sol.append((x,-y))\n",
    "                    elif y==0:\n",
    "                        sol.append((x,y))\n",
    "                        sol.append((-x,y))\n",
    "                    else:\n",
    "                        sol.append((x,y))\n",
    "                        sol.append((-x,y))\n",
    "                        sol.append((x,-y))\n",
    "                        sol.append((-x,-y))\n",
    "            return sol\n",
    "        else:\n",
    "            print \"Tenemos una ecuación trivial, mete un n válido\"\n",
    "            return false\n",
    "    else:\n",
    "        #Si el d es negativo llamamos a la de la práctica anterior\n",
    "        return eqpell(n,d)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(2, 1), (-2, 1), (2, -1), (-2, -1), (1, 0), (-1, 0)]"
      ]
     },
     "execution_count": 34,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "generalpell(1,3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "101"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#Comprobamos el resultado\n",
    "26**2-23*5**2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[]"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#Esta no tiene solución\n",
    "generalpell(12,5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(3, 1), (-3, 1), (3, -1), (-3, -1)]"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "generalpell(2,7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 38,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#Comprobamos que da solución\n",
    "3**2-7*1**2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Resto de las funciones auxiliares que involucran la resolución de ecuaciones de Pell."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Ejercicio 6.-** Redefine las siguientes funciones de la tarea factDE1 para que funcionen tanto para $d<0$ como para $d>0$:\n",
    "\n",
    "- <span style=\"color:red\">es_irreducible($\\alpha$,d)</span>,\n",
    "- <span style=\"color:red\">connorma(n,d)</span>."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def es_irreducible2(alpha,d):\n",
    "    #Comprobamos si alpha es irreducible en O, para ello vemos primero si es entero\n",
    "    if es_entero2(alpha,d)==false:\n",
    "        print \"No es entero algebraico alpha\"\n",
    "        return false\n",
    "    norm_alpha=abs(norma2(alpha,d))\n",
    "    #Miramos si la norma en valor absoluto es un primo de Z\n",
    "    if isprime(norm_alpha)==true:\n",
    "        return true\n",
    "    #A continuación comprobamos sí la norma no es un cuadrado perfecto\n",
    "    elif ask(Q.integer(sqrt(norm_alpha)))==false:\n",
    "        return false\n",
    "    #Si es un cuadrado perfecto, vemos si es de la forma un primo al cuadrado\n",
    "    elif isprime(sqrt(norm_alpha)):\n",
    "        #Comprobamos si hay elementos con más o menos la norma de la raíz de la norma de alpha que es un primo\n",
    "        if connorma2(sqrt(norm_alpha),d)==[] and connorma2(-sqrt(norm_alpha),d)==[]:\n",
    "            return true\n",
    "        else:\n",
    "            return false\n",
    "    else:\n",
    "        return false"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def connorma2(n,d):\n",
    "    #Calculamos los elementos con norma n en O, para ello reslvemos la ecuación de Pell general\n",
    "    elementos=[]\n",
    "    if d%4!=1:\n",
    "        sol=generalpell(n,d)\n",
    "        for i in range (0,len(sol)):\n",
    "            a=sol[i][0]+sol[i][1]*sqrt(d)\n",
    "            elementos.append(a)\n",
    "        return elementos\n",
    "    else:\n",
    "        sol=generalpell(4*n,d)\n",
    "        for i in range (0,len(sol)):\n",
    "            x=sol[i][0]\n",
    "            y=sol[i][1]\n",
    "            if((x-y)%2==0):\n",
    "                a=Rational(x,2)+Rational(y,2)*sqrt(d)\n",
    "                elementos.append(a)\n",
    "        return elementos"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- ** Imput: ** Un entero algebraico $\\alpha\\in \\mathbb Q(\\sqrt d)$ que no es una unidad, con $d$ un entero libre de cuadrados tal que el anillo de enteros de $\\mathbb Q(\\sqrt d)$ es un DE.\n",
    "- ** Output: ** Una lista de enteros irreducibles $[\\alpha_1,\\ldots,\\alpha_r]$ tal que $\\alpha=\\alpha_1\\ldots \\alpha_r$.\n",
    "\n",
    "   - ** Paso 1.-** Calcular la norma de $\\alpha$ y factorizarla en $\\mathbb Z$,\n",
    "   $$norma(\\alpha)=p_1^{e_1} p_2^{e_2}\\ldots p_s^{e_s}.$$\n",
    "   - ** Paso 2.-** Calculamos la lista de enteros con norma $p_1$:\n",
    "   $$L=connorma(p_1,d)$$\n",
    "        - Si $L=\\emptyset$ entonces $p_1$ es irreducible, comprobamos si $\\alpha_1=p_1$ divide a $\\alpha$.\n",
    "        - En otro caso, para cada $\\alpha_1\\in L$ comprobamos si $\\alpha_1$ divide a $\\alpha$.\n",
    "   \n",
    "   Si $s>1$ en el paso 2 debemos encontrar un divisor propio $\\alpha_1$ de $\\alpha$. Tomamos \n",
    "   $$\\alpha=cociente(\\alpha_1,\\alpha)$$\n",
    "      y volvemos al paso 1. \n",
    "\n",
    "El algoritmo acaba cuando $\\alpha$ es unidad o irreducible."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "** Ejercicio 7.-** Toma como $k$ el número de tu DNI o pasaporte (quita todas las letras) y toma $d$ el entero libre de cuadrados que no sea congruente con 1 módulo 4 más cercano a $k%100$.\n",
    "\n",
    "Elije $\\alpha$ un entero en $\\mathbb Q(\\sqrt d)$ y factorizalo aplicando el algoritmo anterior paso a paso. Asegúrate de elegir un $\\alpha$ con al menos tres factores. Asegúrate también que la factorización que obtienes es correcta."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Nota:\n",
    "Es importante que se vaya ejecutando secuencialmente ya que se van modificando variables, en otro caso podría dar errores."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3\n",
      "Nuestro n es  385*sqrt(19) + 1848 con norma  598829  norma que factoriza como  {11: 2, 101: 1, 7: 2}\n"
     ]
    }
   ],
   "source": [
    "#El d más cercano a 39 que nos congruente con 1 mod 4 es 19\n",
    "print 19%4\n",
    "d=19\n",
    "#Hacemos la elección del n que queremos factorizar\n",
    "n=7*11*(24+5*sqrt(19))\n",
    "print \"Nuestro n es \",n,\"con norma \",norma2(n,d),\" norma que factoriza como \", factorint(norma2(n,d))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Los elementos con norma 7 son  []\n",
      "Los elementos con norma -7 son  []\n"
     ]
    }
   ],
   "source": [
    "#Una lista donde guardar los factores de n\n",
    "factores=[]\n",
    "#Elementos con norma 7\n",
    "L1=connorma2(7,d)\n",
    "print \"Los elementos con norma 7 son \",L1\n",
    "L1=connorma2(-7,d)\n",
    "print \"Los elementos con norma -7 son \",L1\n",
    "#No hay elementos con norma 7 o -7 luego vamos a tener que buscar elementos con norma 49"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Los elementos con norma 49 Y -49 son  [7, -7]\n",
      "True\n",
      "True\n",
      "Nuestro n ahora es  55*sqrt(19) + 264 con norma  12221  norma que factoriza como  {11: 2, 101: 1}\n"
     ]
    }
   ],
   "source": [
    "#Elementos con norma 49\n",
    "L1=connorma2(49,d)\n",
    "L1=L1+connorma2(-49,d)\n",
    "print \"Los elementos con norma 49 Y -49 son \",L1\n",
    "#Comprobamos que 7 es irreducible\n",
    "print es_irreducible2(7,d)\n",
    "#Comprobamos que 7 divide a nuesto n\n",
    "print divide2(7,n,d)\n",
    "#Hacemos la división y nos quedamos con nuestro nuevo n\n",
    "n=cociente2(7,n,d)\n",
    "print \"Nuestro n ahora es \",n,\"con norma \",norma2(n,d),\" norma que factoriza como \", factorint(norma2(n,d))\n",
    "#Añadimos 7 a la lista de factores\n",
    "factores.append(7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Los elementos con norma 11 son  []\n",
      "Los elementos con norma 11 son  []\n"
     ]
    }
   ],
   "source": [
    "#Elementos con norma 11 y -11\n",
    "L2=connorma2(11,d)\n",
    "print \"Los elementos con norma 11 son \",L2\n",
    "L2=connorma2(-11,d)\n",
    "print \"Los elementos con norma 11 son \",L2\n",
    "#Comprobamos que no hay elementos con norma 11"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Los elementos con norma 121 Y -121 son  [11, -11]\n",
      "True\n",
      "True\n",
      "Nuestro n ahora es  5*sqrt(19) + 24 con norma  101  norma que factoriza como  {101: 1}\n"
     ]
    }
   ],
   "source": [
    "#Elementos con norma 121 y -121\n",
    "L2=connorma2(121,d)\n",
    "L2=L2+connorma2(-121,d)\n",
    "print \"Los elementos con norma 121 Y -121 son \",L2\n",
    "#Vemos si 11 es irreducible\n",
    "print es_irreducible2(11,d)\n",
    "#Comprobamos si divide al n que nos queda\n",
    "print divide2(11,n,d)\n",
    "#Nos quedamos con un nuevo n\n",
    "n=cociente2(11,n,d)\n",
    "print \"Nuestro n ahora es \",n,\"con norma \",norma2(n,d),\" norma que factoriza como \", factorint(norma2(n,d))\n",
    "#Añadimos el 11 a nuestra lista de factores\n",
    "factores.append(11)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Los elementos con norma 101 Y -101 son  [5*sqrt(19) + 24, -24 + 5*sqrt(19), -5*sqrt(19) + 24, -24 - 5*sqrt(19)]\n",
      "True\n",
      "True\n",
      "Nuestro n ahora es  1 con norma  1  norma que factoriza como  {}\n",
      "Los factores de n son  [7, 11, 5*sqrt(19) + 24]\n"
     ]
    }
   ],
   "source": [
    "#Elementos con norma 101 y -101\n",
    "L3=connorma2(101,d)\n",
    "L3=L3+connorma2(-101,d)\n",
    "print \"Los elementos con norma 101 Y -101 son \",L3\n",
    "#Comprobamos que es irreducible uno de los elementos de la lista\n",
    "print es_irreducible2(24+5*sqrt(19),d)\n",
    "#Comprobamos si divide\n",
    "print divide2(24+5*sqrt(19),n,d)\n",
    "#Calculamos el cociente\n",
    "n=cociente2(24+5*sqrt(19),n,d)\n",
    "print \"Nuestro n ahora es \",n,\"con norma \",norma2(n,d),\" norma que factoriza como \", factorint(norma2(n,d))\n",
    "#Añadimos el número a nuestra lista de factores\n",
    "factores.append(24+5*sqrt(19))\n",
    "#Nos queda una unidad, 1, por lo cual ya tenemos una factorización de n\n",
    "print \"Los factores de n son \",factores\n",
    "#Vemos que es correcto ya que son los tres factores que hemos multiplicado\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "** Ejercicio 8.-** Toma como $k$ el número de tu DNI o pasaporte (quita todas las letras) y toma $d$ el entero libre de cuadrados que sea congruente con 1 módulo 4 más cercano a $k%100$.\n",
    "\n",
    "Elije $\\alpha$ un entero en $\\mathbb Q(\\sqrt d)$ y factorizalo aplicando el algoritmo anterior paso a paso. Asegúrate de elegir un $\\alpha$ con al menos tres factores. Asegúrate también que la factorización que obtienes es correcta."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1\n",
      "-117*sqrt(37) + 740 41107 {11: 1, 37: 1, 101: 1}\n"
     ]
    }
   ],
   "source": [
    "#El d más cercano congruente con 1 módulo 4 es 37\n",
    "print 37%4\n",
    "d=37\n",
    "n=simplify((Rational(-21,2)+Rational(1,2)*sqrt(37))*(6*sqrt(37)-37)*(Rational(9,2)+Rational(1,2)*sqrt(37)))\n",
    "#Vemos el n, y la norma de n y vemos la factorización de su norma\n",
    "print n,norma2(n,d),factorint(norma2(n,d))\n",
    "#Iniciamos la lista de factores\n",
    "factores=[]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Los elementos con norma +11 Y -11 son  [sqrt(37)/2 + 9/2, -9/2 + sqrt(37)/2, -sqrt(37)/2 + 9/2, -9/2 - sqrt(37)/2, 17/2 + 3*sqrt(37)/2, -17/2 + 3*sqrt(37)/2, -3*sqrt(37)/2 + 17/2, -3*sqrt(37)/2 - 17/2]\n",
      "Los factores de nuestro n son  [sqrt(37)/2 + 9/2]\n",
      "El n que tenemos ahora es  -163*sqrt(37)/2 + 999/2 los primos que dividen a la norma de n son  [37, 101]\n"
     ]
    }
   ],
   "source": [
    "#Elementos con norma 11 y -11\n",
    "L1=connorma2(11,d)\n",
    "L1=L1+connorma2(-11,d)\n",
    "print \"Los elementos con norma +11 Y -11 son \",L1\n",
    "for i in range(0,len(L1)):\n",
    "    #Vemos si es irreducible los elementos de L1\n",
    "    if es_irreducible2(L1[i],d):\n",
    "        #Si es irreducible, comprobamos si divide a nuestro n\n",
    "        if(divide2(L1[i],n,d))==true:\n",
    "            #Si divide al n, añadimos el elemento a la lista de factores, y asignamos a n el valor del cociente\n",
    "            factores.append(L1[i])\n",
    "            n=cociente2(L1[i],n,d)\n",
    "            break\n",
    "print \"Los factores de nuestro n son \",factores\n",
    "print \"El n que tenemos ahora es \",n, \"los primos que dividen a la norma de n son \",list(factorint(norma2(n,d)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Los elementos con norma 37 Y -37 son  [6*sqrt(37) + 37, -37 + 6*sqrt(37), -6*sqrt(37) + 37, -37 - 6*sqrt(37), sqrt(37), -sqrt(37)]\n",
      "Los factores de nuestro n son  [sqrt(37)/2 + 9/2, 6*sqrt(37) + 37]\n",
      "El n que tenemos ahora es  -325*sqrt(37)/2 + 1977/2 los primos que dividen a la norma de n son  [101]\n"
     ]
    }
   ],
   "source": [
    "#Elementos con norma 37 y -37\n",
    "L2=connorma2(37,d)\n",
    "L2=L2+connorma2(-37,d)\n",
    "print \"Los elementos con norma 37 Y -37 son \",L2\n",
    "for i in range(0,len(L2)):\n",
    "    #Vemos si es irreducible los elementos de L2\n",
    "    if es_irreducible2(L2[i],d):\n",
    "        #Si es irreducible, comprobamos si divide a nuestro n\n",
    "        if(divide2(L2[i],n,d))==true:\n",
    "            #Si divide al n, añadimos el elemento a la lista de factores,y asignamos a n el valor del cociente\n",
    "            factores.append(L2[i])\n",
    "            n=cociente2(L2[i],n,d)\n",
    "            break\n",
    "print \"Los factores de nuestro n son \",factores\n",
    "print \"El n que tenemos ahora es \",n, \"los primos que dividen a la norma de n son \",list(factorint(norma2(n,d)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Los elementos con norma 101 Y -101 son  [sqrt(37)/2 + 21/2, -21/2 + sqrt(37)/2, -sqrt(37)/2 + 21/2, -21/2 - sqrt(37)/2, 89/2 + 15*sqrt(37)/2, -89/2 + 15*sqrt(37)/2, -15*sqrt(37)/2 + 89/2, -15*sqrt(37)/2 - 89/2]\n",
      "Los factores de nuestro n son  [sqrt(37)/2 + 9/2, 6*sqrt(37) + 37, -21/2 + sqrt(37)/2]\n",
      "El n que tenemos ahora es  -73 + 12*sqrt(37) los primos que dividen a la norma de n son  []\n"
     ]
    }
   ],
   "source": [
    "#Elementos con norma 101 y -101\n",
    "L3=connorma2(101,d)\n",
    "L3=L3+connorma2(-101,d)\n",
    "print \"Los elementos con norma 101 Y -101 son \",L3\n",
    "for i in range(0,len(L3)):\n",
    "    #Vemos si es irreducible los elementos de L3\n",
    "    if es_irreducible2(L3[i],d):\n",
    "        #Si es irreducible, comprobamos si divide a nuestro n\n",
    "        if(divide2(L3[i],n,d))==true:\n",
    "            #Si divide al n, añadimos el elemento a la lista de factores,y asignamos a n el valor del cociente\n",
    "            factores.append(L3[i])\n",
    "            n=cociente2(L3[i],n,d)\n",
    "            break\n",
    "print \"Los factores de nuestro n son \",factores\n",
    "print \"El n que tenemos ahora es \",n, \"los primos que dividen a la norma de n son \",list(factorint(norma2(n,d)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n",
      "Los factores de nuestro n son  [sqrt(37)/2 + 9/2, 6*sqrt(37) + 37, -21/2 + sqrt(37)/2, -73 + 12*sqrt(37)]\n",
      "Este es el n que hemos factorizado  -117*sqrt(37) + 740\n"
     ]
    }
   ],
   "source": [
    "#Vemos si el n que nos queda es una unidad\n",
    "print es_unidad2(n,d)\n",
    "#Añadimos la unidad a nuestra lista de factores\n",
    "factores.append(n)\n",
    "print \"Los factores de nuestro n son \",factores\n",
    "#Comprobamos efectivamente que lo hemos factorizado\n",
    "n1=1\n",
    "for i in range(0,len(factores)):\n",
    "    n1=simplify(n1*factores[i])\n",
    "print \"Este es el n que hemos factorizado \",n1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## Nota:\n",
    "\n",
    "Comprueba que la función <span style=\"color:red\">factoriza($\\alpha$,d)</span> funciona tanto para $d$ positivo como negativo. Coge los ejemplos de la práctica anterior y mira que se obtiene el mismo resultado."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "** Ejercicio 9 (Avanzado).-** Define una función <span style=\"color:red\">factoriza($\\alpha$,d)</span> para factorizar un elemento $\\alpha$ en el anillo de enteros de $\\mathbb Q (\\sqrt d )$, que funcione tanto para $d<0$ como para $d>0$. Aplica esta función a los elementos factorizados en los ejercicios 7 y 8, y asegúrate de que obtienes resultados compatibles."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def factoriza2(alpha,d):\n",
    "    if d==0:\n",
    "        print \"Elige un d distinto de 0\"\n",
    "        return false\n",
    "    if d<0:\n",
    "        #Devolvemos un diccionario con los factores de alpha y sus exponentes\n",
    "        return dict(factoriza(alpha,d))\n",
    "    else:\n",
    "        if es_irreducible2(alpha,d):\n",
    "            print \"Es irreducible\"\n",
    "            return false     \n",
    "        #Calculamos la norma de n y la lista con los factores de la norma\n",
    "        norm=norma2(alpha,d)\n",
    "        fact=list(factorint(norm))\n",
    "        factores=[]\n",
    "        #Por cada factor de la norma de alpha vemos si algún elemento de esa norma divide a alpha\n",
    "        for i in range(0,len(fact)):\n",
    "            L1=connorma2(fact[i],d)\n",
    "            L1=L1+connorma2(-fact[i],d)\n",
    "            bool1=false\n",
    "            for j in range(0,len(L1)):\n",
    "                while(divide2(L1[j],alpha,d))==true:\n",
    "                    #Añadimos el elemento a la lista de factores si divide a alpha\n",
    "                    factores.append(L1[j])\n",
    "                    alpha=cociente2(L1[j],alpha,d)\n",
    "                    bool1=true\n",
    "                    #Cuando nos quede una unidad paramos de iterar\n",
    "                    if es_unidad2(alpha,d):\n",
    "                        factores.append(alpha)\n",
    "                        break\n",
    "            if bool1==false:\n",
    "                #Esta condición es por si no hay irreducibles de norma p, buscarlos de p^2\n",
    "                L1=connorma2(fact[i]**2,d)\n",
    "                for j in range(0,len(L1)):\n",
    "                    while(divide2(L1[j],alpha,d))==true:\n",
    "                        #Añadimos el elemento a la lista de factores si divide a alpha\n",
    "                        factores.append(L1[j])\n",
    "                        alpha=cociente2(L1[j],alpha,d)\n",
    "                        #Cuando tengamos una unidad paramos de iterar\n",
    "                        if es_unidad2(alpha,d):\n",
    "                            factores.append(alpha)\n",
    "                            break\n",
    "        #Contamos cuantas veces sale cada factor para que aparezca junto a él su exponente\n",
    "        factores=contador(factores)\n",
    "        #Convertimos la lista de factores en un diccionario\n",
    "        return dict(factores)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Nuestro número es  385*sqrt(19) + 1848\n",
      "Su factorización es  {1: 1, 11: 1, 5*sqrt(19) + 24: 1, 7: 1}\n",
      "Qué son exactamente los factores que hemos usado y que hemos obtenido en el ejercicio 7\n"
     ]
    }
   ],
   "source": [
    "n=(7*11*(24+5*sqrt(19)))\n",
    "print \"Nuestro número es \",n\n",
    "print \"Su factorización es \",factoriza2(n,19)\n",
    "print \"Qué son exactamente los factores que hemos usado y que hemos obtenido en el ejercicio 7\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Nuestro número es  -117*sqrt(37) + 740\n",
      "Su factorización es  {6*sqrt(37) + 37: 1, -73 + 12*sqrt(37): 1, sqrt(37)/2 + 9/2: 1, -21/2 + sqrt(37)/2: 1}\n",
      "Que son los factores obtenidos en el ejercicio 8 en el cual comprobamos que era una factorización del número:  [sqrt(37)/2 + 9/2, 6*sqrt(37) + 37, -21/2 + sqrt(37)/2, -73 + 12*sqrt(37)]\n"
     ]
    }
   ],
   "source": [
    "n=simplify((Rational(-21,2)+Rational(1,2)*sqrt(37))*(6*sqrt(37)-37)*(Rational(9,2)+Rational(1,2)*sqrt(37)))\n",
    "print \"Nuestro número es \",n\n",
    "print \"Su factorización es \",factoriza2(n,37)\n",
    "print \"Que son los factores obtenidos en el ejercicio 8 en el cual comprobamos que era una factorización del número: \",factores"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Veamos que ocurre con potencias\n",
      "Nuestro número es  -2737666704*sqrt(37) + 16652620081\n",
      "Su factorización es  {6*sqrt(37) + 37: 2, -1752*sqrt(37) + 10657: 1, -21/2 + sqrt(37)/2: 6}\n",
      "Comprobamos que es una factorización  -2737666704*sqrt(37) + 16652620081\n"
     ]
    }
   ],
   "source": [
    "print \"Veamos que ocurre con potencias\"\n",
    "n=expand(simplify(((Rational(-21,2)+Rational(1,2)*sqrt(37))**6)*((6*sqrt(37)-37))**2))\n",
    "print \"Nuestro número es \",n\n",
    "print \"Su factorización es \",factoriza2(n,37)\n",
    "print \"Comprobamos que es una factorización \", expand(simplify(((Rational(-21,2)+Rational(1,2)*sqrt(37))**6)*((6*sqrt(37)+37))**2)*(-1752*sqrt(37)+10657))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Pasémosle a la función a los ejemplos de la práctica pasada para comprobar que puede con todo."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{-1/2 + sqrt(3)*I/2: 1, 3/2 + sqrt(3)*I/2: 8}\n",
      "81\n"
     ]
    }
   ],
   "source": [
    "print factoriza2(81,-3)\n",
    "#Veamos que es correcta la solución\n",
    "print simplify(expand(pow(Rational(3,2)+Rational(1,2)*sqrt(-3),8))*(Rational(-1,2)+Rational(1,2)*sqrt(-3)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "{1: 1, 17/2 + 3*sqrt(11)*I/2: 1, 9/2 + sqrt(11)*I/2: 1, 5/2 + 3*sqrt(11)*I/2: 1}\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "-213/2 + 145*sqrt(11)*I/2"
      ]
     },
     "execution_count": 57,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "print factoriza2(Rational(-213,2)+Rational(145,2)*sqrt(-11),-11)\n",
    "#Comprobamos que es buena la factorización\n",
    "simplify((Rational(17,2)+Rational(3,2)*sqrt(-11))*(Rational(5,2)+Rational(3,2)*sqrt(-11))*(Rational(9,2)+Rational(1,2)*sqrt(-11)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[sqrt(3) + 2, -2 + sqrt(3), -sqrt(3) + 2, -2 - sqrt(3), 1, -1]"
      ]
     },
     "execution_count": 58,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "connorma2(1,3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(2, 0)"
      ]
     },
     "execution_count": 59,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "ab2(2,2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{-6 + sqrt(19): 1,\n",
       " -9 + 2*sqrt(19): 1,\n",
       " -57799 + 13260*sqrt(19): 1,\n",
       " 4 + sqrt(19): 1,\n",
       " 2*sqrt(19) + 9: 2,\n",
       " 13 + 3*sqrt(19): 3}"
      ]
     },
     "execution_count": 60,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "factoriza2(-230+10*sqrt(19),19)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 71,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "51000"
      ]
     },
     "execution_count": 71,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "\n",
    "(norma2(-230+10*sqrt(19),19))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "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.5.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}