Práctica 7 - Factorización en DE1.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 \n",
    "$d=-1,-2,-3,-7,-11$.\n",
    "\n",
    "- **Caso 1.-**  $\\quad d = -1,-2$.  Tenemos $d \\not\\equiv 1 \\mbox{ mod } 4$ y por tanto $\\mathbb{O}=\\mathbb{Z}[\\sqrt{d}]$.\n",
    "\n",
    "- **Caso 2.-**  $\\quad d =-3,-7,-11$. Tenemos $d \\equiv 1 \\mbox{ mod } 4$ y por tanto $\\mathbb{O}=\\mathbb{Z}[\\frac{1+\\sqrt{d}}{2}]$.\n",
    "\n",
    "Para poder llevar una notación homogénea en los dos casos vamos a denotar \n",
    "$$ \n",
    "e = \\sqrt d \\quad\\mbox{si}\\quad d=-1,-2 \\quad  \\mbox{y} \\quad e = \\frac{1+\\sqrt d}{2} \\quad \\mbox{ en otro caso.}\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": [
    "En Python la $i$ compleja se denota por $j$,  $J$ o también $I$. Un complejo puede introducirse al menos de dos maneras:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "alpha= 3+5j"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "complex"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "type(alpha)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "beta=complex(2,-3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "complex"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "type(beta)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Podemos operar con ellos independientemente de como los hayamos introducido."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(5+2j)"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "alpha+beta"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(21+1j)"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "alpha*beta"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Podemos recuperar la parte real o la imaginaria, o calcular conjugados"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3.0"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "alpha.real"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "-3.0"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "beta.imag"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(3-5j)"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "alpha.conjugate()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(2+3j)"
      ]
     },
     "execution_count": 11,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "beta.conjugate()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Importamos sympy para poder trabajar con raíces"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "from sympy import *"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Vamos a introducir generadores del anillo de enteros, uno de cada tipo."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "e1=sqrt(-2)\n",
    "e2=(-1+sqrt(-3))/2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "sqrt(2)*I\n",
      "-1/2 + sqrt(3)*I/2\n"
     ]
    }
   ],
   "source": [
    "print e1\n",
    "print e2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Veamos de que tipo son los datos que hemos introducido"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "sympy.core.mul.Mul"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "type(e1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "sympy.core.add.Add"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "type(e2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Podemos ver que e1 y e2 no son tratados como complejos y por tanto algunas funciones para complejos no funcionan"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "#e1.real"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Pero otras si"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "-sqrt(2)*I"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "e1.conjugate()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Y podemos trabajar con ellos"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    "alpha1=expand((3-4*e1)*(1-2*e1))\n",
    "alpha2=expand((2-5*e2)*(4-3*e2))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "-13 - 10*sqrt(2)*I\n"
     ]
    }
   ],
   "source": [
    "print alpha1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "27/2 - 41*sqrt(3)*I/2\n"
     ]
    }
   ],
   "source": [
    "print(alpha2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## ¡¡¡ Cuidado con el operador <span style=\"color:red\">/</span>  !!!!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [],
   "source": [
    "a=1/2 +(5/2)*sqrt(-3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2*sqrt(3)*I"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Python ha tomado 1/2=0 y 5/2=2,  que no es lo que queremos. La forma en que Python trabaja con racionales es un poco \"patatera?¿?\" así que cuidado con cómo introducís un elemento de $\\mathbb Q (\\sqrt d)$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "aa=Rational(1,2)+Rational(5,2)*sqrt(-3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1/2 + 5*sqrt(3)*I/2"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "aa"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Podemos operar con este valor, por ejemplo:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "59/2 - 57*sqrt(3)*I/2"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "5*aa+2*alpha2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(1/2 + 5*sqrt(3)*I/2)*(27/2 - 41*sqrt(3)*I/2)"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "aa*alpha2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "321/2 + 47*sqrt(3)*I/2"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "simplify(aa*alpha2)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## ¿Es entero?"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Para ver si un elemento $\\alpha \\in \\mathbb{Q}(\\sqrt d )$ es entero tenemos dos opciones:\n",
    " - Calcular la norma y la traza de $\\alpha$ y ver que están en $\\mathbb Z$, o bien,\n",
    " - Calcular el polinomio mínimo de $\\alpha$ y ver que está en $\\mathbb Z [x]$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "** Ejercicio 1.-** Define funciones:\n",
    " - <span style=\"color:red\">norma($\\alpha$), traza($\\alpha$)</span> para calcular la norma y la traza de un elemento en $\\mathbb{Q}(\\sqrt d)$.\n",
    " - <span style=\"color:red\">es_entero($\\alpha$)</span> con salida true o false dependiendo de si $\\alpha$ es o no entero algebraico."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def norma(alpha):\n",
    "    #Función para calcular la norma de un elemento alpha\n",
    "    norma=simplify(alpha*alpha.conjugate())\n",
    "    return norma"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [],
   "source": [
    "def traza(alpha):\n",
    "    #Función para calcular la traza de un elemento alpha\n",
    "    traza=simplify(alpha+alpha.conjugate())\n",
    "    return traza"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [],
   "source": [
    "def es_entero(alpha):\n",
    "    #Comprobamos si el elemento alpha es entero algebraico o no\n",
    "    norm=norma(alpha)\n",
    "    traz=traza(alpha)\n",
    "    #Comprobamos si la norma y la traza son enteras \n",
    "    if ask(Q.integer(traz))and ask(Q.integer(norm)):\n",
    "        return true\n",
    "    else:\n",
    "        return false"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1/2 + 5*sqrt(3)*I/2 19 1 <class 'sympy.core.numbers.One'> False\n"
     ]
    }
   ],
   "source": [
    "print aa,norma(aa),traza(aa),type(traza(aa)),es_entero(sqrt(2))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Enteros"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Cualquier elemento $\\alpha \\in \\mathbb Q (\\sqrt d)$ se escribe de la forma $\\alpha=x+y*\\sqrt d$ con $x,y\\in \\mathbb Q$. Por otro lado, $\\{1,e\\}$ es una base entera de $\\mathbb Q(\\sqrt d)$ y por tanto,  si $\\alpha$ es un entero, podemos encontrar enteros $a,b\\in\\mathbb Z$ tales que $\\alpha=a + b*e$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Ejercicio 2.-** Define funciones:\n",
    " - <span style=\"color:red\">xy($\\alpha$,d)</span> con salida el par $(x,y)\\in \\mathbb Q^2$ tal que $\\alpha=x+y*\\sqrt d$.\n",
    " - <span style=\"color:red\">ab($\\alpha$,d)</span> que, en el caso de ser $\\alpha$ entero, tenga como salida el par $(a,b)\\in \\mathbb Z^2$ tal que $\\alpha=a+b*e$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def xy(alpha,d):\n",
    "    #Extraemos las coordenadas de alpha en Q(sqrt(d))\n",
    "    x=(alpha+alpha.conjugate())/2\n",
    "    y=(alpha-alpha.conjugate())/(2*sqrt(d))\n",
    "    return(x,y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def ab(alpha,d):\n",
    "    #Comprobamos si alpha es entero, si lo es calculamos sus coordenadas en una base entera\n",
    "    if es_entero(alpha)==true:\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=xy(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",
    "    else:\n",
    "        return\"Introduzca un entero algebraico\""
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Funciones divide y cociente"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Ejercicio 3.-** Define funciones:\n",
    "- <span style=\"color:red\">divide($\\alpha,\\beta$)</span>  con salida true si $\\alpha$ divide a $\\beta$ y false en otro caso.\n",
    "- <span style=\"color:red\">cociente($\\alpha,\\beta$)</span> que en el caso de que $\\alpha$ divida a $\\beta$ calcule el cociente de la división."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [],
   "source": [
    "def divide(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",
    "    num=expand(simplify(beta*alpha.conjugate()))\n",
    "    norm=norma(alpha)\n",
    "    coord=xy(num,d)\n",
    "    division=Rational(coord[0],norm)+Rational(coord[1],norm)*sqrt(d)\n",
    "    return es_entero(division)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def cociente(alpha,beta,d):\n",
    "    #Si alpha divide a beta calculamos su cociente\n",
    "    if divide(alpha,beta,d)!=true:\n",
    "        return false\n",
    "    division=simplify(beta*alpha.conjugate())/norma(alpha)\n",
    "    return division"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## La ecuación de Pell $$x^2-d*y^2=n.$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "En el caso $d<0$ la ecuación de Pell es fácil de resolver. Basta con acotar el valor de $y$, $0\\leq y\\leq \\sqrt{\\frac{n}{-d}}$, y para cada $y$ en ese intervalo comprobar si $n+d*y^2$ es un cuadrado. Notar que si $(x,y)$ es una solución de la ecuación de Pell, también lo serán $(\\pm x,\\pm y)$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "** Ejercicio 4.-** Define una función <span style=\"color:red\">eqpell(n,d)</span> que de una lista con todas las soluciones de la ecuación de Pell. Estamos suponiendo $d<0$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [],
   "source": [
    "def eqpell(n,d):\n",
    "    #Resolución de la ecuación de Pell con d negativo\n",
    "    sol=[]\n",
    "    if d>=0:\n",
    "        return \"Introduce un d negativo\"\n",
    "    ymax=sqrt(n/-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 y==0:\n",
    "                sol.append((x,y))\n",
    "                sol.append((-x,y))\n",
    "            elif x==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"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## Cálculo de elementos con una determinada norma."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Pretendemos ahora calcular elementos en $\\mathbb O$ con una norma determinada. Tendremos que distinguir según estemos en el **caso 1** o en el **caso2**.\n",
    "\n",
    "- **Caso 1.-** $d \\not\\equiv 1 \\mbox{ mod } 4$. Para calcular los elementos con norma $n$ basta con resolver la ecuación de Pell $x^2-d*y^2=n$, cada solución $(x,y)$ de esta ecuación da lugar a un elemento $\\alpha=x+y*\\sqrt d$ con norma $n$.\n",
    "- **Caso 2.-** $d \\equiv 1 \\mbox{ mod } 4$. En este caso los elementos de $\\mathbb O$ son de la forma \n",
    "$$\n",
    "\\alpha = a - b *\\frac{1+\\sqrt d}{2} = \\frac{2a+b + b*\\sqrt d}{2}=\\frac{x+y*\\sqrt d}{2},\n",
    "$$\n",
    "con $x=2a+b$ e $y=b$. Entonces $norma(\\alpha)=\\frac{x^2-d*y^2}{4}$, por tanto para calcular los elementos con norma $n$ resolvemos la ecuación de Pell $x^2-d*y^2=4*n$. Cada solución $(x,y)$ de esta ecuación nos dará un elemento $\\alpha=\\frac{x+y*\\sqrt d}{2}$ de norma $n$, pero tendremos que asegurarnos que $\\alpha$ es entero. Esto lo podemos hacer con la función  <span style=\"color:green\">es_entero</span> o bien comprobando que $x-y$ es par."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "** Ejercicio 5.-** Define una función <span style=\"color:red\">connorma(n,d)</span> para calcular los elementos de $\\mathbb O$ con norma $n$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [],
   "source": [
    "def connorma(n,d):\n",
    "    #Calculamos los elementos con norma n en O\n",
    "    elementos=[]\n",
    "    if d%4!=1:\n",
    "        sol=eqpell(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=eqpell(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\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Unidades e irreducibles"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Un elemento $\\alpha \\in \\mathbb O$ es una ***unidad*** si, y solo si, $norma(\\alpha)=1$.\n",
    "- Un elemento $\\alpha \\in \\mathbb O$ es ***irreducible*** si $norma(\\alpha)$ es primo o bien $norma(\\alpha)$ es un primo al cuadrado y no hay enteros de norma dicho primo.\n",
    "\n",
    "** Ejercicio 6.- ** Define funciones <span style=\"color:red\">es_unidad($\\alpha$,d)</span> y <span style=\"color:red\">es_irreducible($\\alpha$,d)</span> con salidas true o false según $\\alpha$ sea o no unidad e irreducible respectivamente.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def es_unidad(alpha):\n",
    "    #Comprobamos si alpha es unidad\n",
    "    if es_entero(alpha)==false:\n",
    "        print \"No es entero algebraico alpha\"\n",
    "        return false\n",
    "    if norma(alpha)==1:\n",
    "        return true\n",
    "    else:\n",
    "        return false"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [],
   "source": [
    "def es_irreducible(alpha,d):\n",
    "    #Comprobamos si alpha es irreducible en O\n",
    "    if es_entero(alpha)==false:\n",
    "        print \"No es entero algebraico alpha\"\n",
    "        return false\n",
    "    norm_alpha=norma(alpha)\n",
    "    if isprime(norm_alpha)==true:\n",
    "        return true\n",
    "    elif isprime(sqrt(norm_alpha)):\n",
    "        if connorma(sqrt(norm_alpha),d)==[]:\n",
    "            return true\n",
    "        else:\n",
    "            return false\n",
    "    else:\n",
    "        return false"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Algoritmo de factorización."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- ** Imput: ** Un entero algebraico $\\alpha\\in \\mathbb Q(\\sqrt d)$ con $d=-1,-2,-3,-7,-11$, que no es una unidad.\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= -1$ si $k$ es impar o $d=-2$ si $k$ es par.\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.\n",
    "\n",
    "** Ejercicio 8.-** Toma como $k$ el número de tu DNI o pasaporte (quita todas las letras) módulo 3 y toma $d= -3,-7,-11$ según $k$ sea 0, 1 o 2 respectivamente. \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": [
    "### Ejercicio 7: Factorizando en $\\mathbb Q $(i)\n",
    "#### Nota:\n",
    "Es importante ir ejecutando las órdenes secuencialmente ya que modifican el n de forma sucesiva, para no llevar a errores"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "23 + 24*I\n"
     ]
    }
   ],
   "source": [
    "#Como mi DNI es 75908039, trabajaremos en -1, y tomamos este n\n",
    "n=simplify((3+2*sqrt(-1))*(4-sqrt(-1))*(2+sqrt(-1)))\n",
    "print n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1105 [17, 5, 13]\n"
     ]
    }
   ],
   "source": [
    "#Calculamos la norma de n y la lista con los factores de la norma\n",
    "norm=norma(n)\n",
    "fact=list(factorint(norm))\n",
    "print norm,fact"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Los elementos con norma 17 son  [4 + I, -4 + I, 4 - I, -4 - I, 1 + 4*I, -1 + 4*I, 1 - 4*I, -1 - 4*I]\n",
      "Los factores de nuestro n son  [-4 + I]\n",
      "El n que tenemos ahora es  -4 - 7*I los primos que dividen a la norma de n son  [5, 13]\n"
     ]
    }
   ],
   "source": [
    "#Una lista donde guardar los factores de n\n",
    "factores=[]\n",
    "#Elementos con norma 17\n",
    "L1=connorma(17,-1)\n",
    "print \"Los elementos con norma 17 son \",L1\n",
    "#Comprobamos si alguno divide a nuestro n\n",
    "for i in range(0,len(L1)):\n",
    "    if(divide(L1[i],n,-1))==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=cociente(L1[i],n,-1)\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(norma(n)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Los elementos con norma 13 son  [3 + 2*I, -3 + 2*I, 3 - 2*I, -3 - 2*I, 2 + 3*I, -2 + 3*I, 2 - 3*I, -2 - 3*I]\n",
      "Los factores de nuestro n son  [-4 + I, 3 + 2*I]\n",
      "El n que tenemos ahora es  -2 - I los primos que dividen a la norma de n son  [5]\n"
     ]
    }
   ],
   "source": [
    "#Elementos con norma 13\n",
    "L2=connorma(13,-1)\n",
    "print \"Los elementos con norma 13 son \",L2\n",
    "#Comprobamos si alguno divide a nuestro n\n",
    "for i in range(0,len(L2)):\n",
    "    if(divide(L2[i],n,-1))==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=cociente(L2[i],n,-1)\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(norma(n)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Los elementos con norma 5 son  [2 + I, -2 + I, 2 - I, -2 - I, 1 + 2*I, -1 + 2*I, 1 - 2*I, -1 - 2*I]\n",
      "Los factores de nuestro n son  [-4 + I, 3 + 2*I, 2 + I]\n",
      "El n que tenemos ahora es  -1 los primos que dividen a la norma de n son  []\n"
     ]
    }
   ],
   "source": [
    "#Elementos con norma 5\n",
    "L3=connorma(5,-1)\n",
    "print \"Los elementos con norma 5 son \",L3\n",
    "#Comprobamos si alguno divide a nuestro n\n",
    "for i in range(0,len(L3)):\n",
    "    if(divide(L3[i],n,-1))==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=cociente(L3[i],n,-1)\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(norma(n)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [],
   "source": [
    "#No tenemos primos que dividan a la norma del nuevo n, comprobamos si es una unidad\n",
    "es_unidad(n)\n",
    "#Añadimos la unidad a los factores\n",
    "factores.append(-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[-4 + I, 3 + 2*I, 2 + I, -1]\n"
     ]
    }
   ],
   "source": [
    "#Como nos queda una unidad ya tenemos la descomposición en primos hecha que es\n",
    "print factores"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Ejercicio 8: Factorizando en $\\mathbb Q $($\\sqrt{-11})$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "-213/2 + 145*sqrt(11)*I/2\n"
     ]
    }
   ],
   "source": [
    "#Como mi DNI es 75908039, trabajaremos en -11, y tomamos este n2\n",
    "n2=simplify((Rational(17,2)+Rational(3,2)*sqrt(-11))*(Rational(9,2)+Rational(1,2)*sqrt(-11))*(Rational(5,2)+Rational(3,2)*sqrt(-11)))\n",
    "print n2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "69161 [97, 31, 23]\n"
     ]
    }
   ],
   "source": [
    "#Calculamos la norma de n y la lista con los factores de la norma\n",
    "norm=norma(n2)\n",
    "fact=list(factorint(norm))\n",
    "print norm,fact"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Los elementos con norma 97 son  [17/2 + 3*sqrt(11)*I/2, -17/2 + 3*sqrt(11)*I/2, 17/2 - 3*sqrt(11)*I/2, -17/2 - 3*sqrt(11)*I/2]\n",
      "Los factores de nuestro n2 son  [17/2 + 3*sqrt(11)*I/2]\n",
      "El n2 que tenemos ahora es  3 + 8*sqrt(11)*I los primos que dividen a la norma de n2 son  [31, 23]\n"
     ]
    }
   ],
   "source": [
    "#Una lista donde guardar los factores de n2\n",
    "factores=[]\n",
    "#Elementos con norma 97\n",
    "L1=connorma(97,-11)\n",
    "print \"Los elementos con norma 97 son \",L1\n",
    "#Comprobamos si alguno divide a nuestro n2\n",
    "for i in range(0,len(L1)):\n",
    "    if(divide(L1[i],n2,-11))==true:\n",
    "        #Si divide al n2, añadimos el elemento a la lista de factores,y asignamos a n2 el valor del cociente\n",
    "        factores.append(L1[i])\n",
    "        n2=cociente(L1[i],n2,-11)\n",
    "        break\n",
    "print \"Los factores de nuestro n2 son \",factores\n",
    "print \"El n2 que tenemos ahora es \",n2, \"los primos que dividen a la norma de n2 son \",list(factorint(norma(n2)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Los elementos con norma 31 son  [17/2 + 3*sqrt(11)*I/2, -17/2 + 3*sqrt(11)*I/2, 17/2 - 3*sqrt(11)*I/2, -17/2 - 3*sqrt(11)*I/2]\n",
      "Los factores de nuestro n2 son  [17/2 + 3*sqrt(11)*I/2, 5/2 + 3*sqrt(11)*I/2]\n",
      "El n2 que tenemos ahora es  9/2 + sqrt(11)*I/2 los primos que dividen a la norma de n2 son  [23]\n"
     ]
    }
   ],
   "source": [
    "#Elementos con norma 31\n",
    "L2=connorma(31,-11)\n",
    "print \"Los elementos con norma 31 son \",L1\n",
    "#Comprobamos si alguno divide a nuestro n2\n",
    "for i in range(0,len(L2)):\n",
    "    if(divide(L2[i],n2,-11))==true:\n",
    "        #Si divide al n2, añadimos el elemento a la lista de factores,y asignamos a n2 el valor del cociente\n",
    "        factores.append(L2[i])\n",
    "        n2=cociente(L2[i],n2,-11)\n",
    "        break\n",
    "print \"Los factores de nuestro n2 son \",factores\n",
    "print \"El n2 que tenemos ahora es \",n2, \"los primos que dividen a la norma de n2 son \",list(factorint(norma(n2)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Los elementos con norma 23 son  [17/2 + 3*sqrt(11)*I/2, -17/2 + 3*sqrt(11)*I/2, 17/2 - 3*sqrt(11)*I/2, -17/2 - 3*sqrt(11)*I/2]\n",
      "Los factores de nuestro n2 son  [17/2 + 3*sqrt(11)*I/2, 5/2 + 3*sqrt(11)*I/2, 9/2 + sqrt(11)*I/2]\n",
      "El n2 que tenemos ahora es  1 los primos que dividen a la norma de n2 son  []\n"
     ]
    }
   ],
   "source": [
    "#Elementos con norma 23\n",
    "L3=connorma(23,-11)\n",
    "print \"Los elementos con norma 23 son \",L1\n",
    "#Comprobamos si alguno divide a nuestro n2\n",
    "for i in range(0,len(L3)):\n",
    "    if(divide(L3[i],n2,-11))==true:\n",
    "        #Si divide al n2, añadimos el elemento a la lista de factores,y asignamos a n2 el valor del cociente\n",
    "        factores.append(L3[i])\n",
    "        n2=cociente(L3[i],n2,-11)\n",
    "        break\n",
    "print \"Los factores de nuestro n2 son \",factores\n",
    "print \"El n2 que tenemos ahora es \",n2, \"los primos que dividen a la norma de n2 son \",list(factorint(norma(n2)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 53,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#No tenemos primos que dividan a la norma del nuevo n2 que es 1, comprobamos si es una unidad\n",
    "es_unidad(n2)\n",
    "#No hace falta añadir la unidad ya que es 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[17/2 + 3*sqrt(11)*I/2, 5/2 + 3*sqrt(11)*I/2, 9/2 + sqrt(11)*I/2]\n"
     ]
    }
   ],
   "source": [
    "#Como nos queda una unidad ya tenemos la descomposición en primos hecha que es\n",
    "print factores"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "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 )$. 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": 55,
   "metadata": {},
   "outputs": [],
   "source": [
    "def contador(lista):\n",
    "    #Función que su input es una lista y su output otra lista\n",
    "    #La lista de salido son duplas con cada elemento de la lista de entrada acompañado con las veces que se repite en la lista de entrada\n",
    "    aux=[]\n",
    "    for i in range(0,len(lista)):\n",
    "        bool1=false\n",
    "        for j in range(0,len(aux)):\n",
    "            if lista[i]==aux[j][0]:\n",
    "                bool1=true\n",
    "        if bool1==false:\n",
    "            count=0\n",
    "            for k in range(0,len(lista)):\n",
    "                if lista[i]==lista[k]:\n",
    "                    count=count+1\n",
    "            aux.append((lista[i],count))\n",
    "    return aux"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "def factoriza(alpha,d):\n",
    "    #Función para factorizar alpha en un dominio euclídeo\n",
    "    if d!=-1 and d!=-2 and d!=-3 and d!=-7 and d!=-11:\n",
    "        print \"Introduce un dominio euclídeo donde pueda factorizar\"\n",
    "        return false\n",
    "    if es_irreducible(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=norma(alpha)\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=connorma(fact[i],d)\n",
    "        bool1=false\n",
    "        for j in range(0,len(L1)):\n",
    "            while(divide(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=cociente(L1[j],alpha,d)\n",
    "                bool1=true\n",
    "                #Cuando nos quede una unidad paramos de iterar\n",
    "                if es_unidad(alpha):\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=connorma(fact[i]**2,d)\n",
    "            for j in range(0,len(L1)):\n",
    "                while(divide(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=cociente(L1[j],alpha,d)\n",
    "                    #Cuando tengamos una unidad paramos de iterar\n",
    "                    if es_unidad(alpha):\n",
    "                        factores.append(alpha)\n",
    "                        break\n",
    "    factores=contador(factores)\n",
    "    return factores\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "Comprobamos que obtenemos los mismos resultados que paso a paso:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[(-4 + I, 1), (2 + I, 1), (3 + 2*I, 1), (-1, 1)]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "23 + 24*I"
      ]
     },
     "execution_count": 57,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "print factoriza(23+24*I,-1)\n",
    "simplify((-4+I)*(2+I)*(3+2*I)*(-1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[(17/2 + 3*sqrt(11)*I/2, 1), (5/2 + 3*sqrt(11)*I/2, 1), (9/2 + sqrt(11)*I/2, 1), (1, 1)]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "-213/2 + 145*sqrt(11)*I/2"
      ]
     },
     "execution_count": 58,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "print factoriza(Rational(-213,2)+Rational(145,2)*sqrt(-11),-11)\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": "markdown",
   "metadata": {},
   "source": [
    "Veamos otros ejemplos: Factoricemos 81 en $Q(\\sqrt{-3})$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(3/2 + sqrt(3)*I/2, 8), (-1/2 + sqrt(3)*I/2, 1)]"
      ]
     },
     "execution_count": 59,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "factoriza(81,-3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "81"
      ]
     },
     "execution_count": 60,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "#Veamos que es correcta la solución\n",
    "simplify(expand(pow(Rational(3,2)+Rational(1,2)*sqrt(-3),8))*(Rational(-1,2)+Rational(1,2)*sqrt(-3)))"
   ]
  }
 ],
 "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
}