Practica 6 - Factor Base .ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# El algoritmo de factorización Factor Base"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from sympy import *"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from itertools import *"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from TANMLP import *"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Elección de la base. Voy a tener suerte"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "La primera elección de la base es poco profesional, por ejemplo elegimos la base con el -1 y los primeros 30 primos."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "** Ejercicio 0.-** Define la base\n",
    "$$B=[-1,2,3,...,113],$$ \n",
    "que tiene al $-1$ y los primeros 30 primos"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def baseprim(b):\n",
    "    #Hacemos una lista con el -1 y los primeros 'b' primos\n",
    "    base=[-1]\n",
    "    for i in range(1,b+1):\n",
    "        base.append(prime(i))\n",
    "    return base"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "Lista de funciones auxiliares que vamos a definir:\n",
    "   - <span style=\"color:red\">abmod(x,n)</span>,\n",
    "   - <span style=\"color:red\">mayorpot(b,p)</span>,\n",
    "   - <span style=\"color:red\">bnumer(b,base,n)</span>,\n",
    "   - <span style=\"color:red\">vec_alfa(b,base,n)</span>,\n",
    "   - <span style=\"color:red\">parp(lista)</span>,\n",
    "   - <span style=\"color:red\">ssuma(lista1,lista2)</span>,\n",
    "   - <span style=\"color:red\">aux(k,r)</span>,\n",
    "   - <span style=\"color:red\">suma(lista,k)</span>,\n",
    "\n",
    "Paso a comentar cada función:\n",
    "\n",
    "  - La función <span style=\"color:red\">abmod(x,n)</span> tiene como salida $x\\%n$ si este es menor o igual que $\\frac{n}{2}$ y $x\\%n -n$ en caso contrario.  \n",
    "  \n",
    "  - La función <span style=\"color:red\">mayorpot(x,p)</span>\n",
    "     - Si $p=-1$ tiene como salida $1$ si $x<0$ y $0$ en caso contrario.\n",
    "     - Para cualquier otro $p$ (normalmente primo) tiene como salida el exponente de la mayor potencia de $p$ que divide a $x$. Para definir esta función no puedes factorizar x.\n",
    "     \n",
    "  - La función <span style=\"color:red\">bnumer(b,base,n)</span> tiene como salida true si $b$ es un base-número relativo a $n$ y false en caso contrario.\n",
    "  \n",
    "  - La función <span style=\"color:red\">vec_alfa(b,base,n)</span> comprueba que $b$ es un base-número y en este caso tiene como salida el vector alfa asociado a $b$. \n",
    "Este será una lista de longitud <span style=\"color:green\">len(base)</span> cuyas coordenadas son los exponentes de los elementos de \"base\" en la descomposición en primos de abmod($b^2,n$) (ver teoría).\n",
    "\n",
    "  - La función <span style=\"color:red\">parp(lista)</span> vale true si todos los elementos en la lista son pares y false en otro caso.\n",
    "  \n",
    "  - La función <span style=\"color:red\">ssuma(lista1,lista2)</span> comprueba que las listas tienen la misma longitud y en ese caso tiene como salida una nueva lista con la misma longitud de las dos listas y que en lugar $i$ tiene a lista1[i]+lista2[i].\n",
    "\n",
    "Nuestro siguiente objetivo es calcular todas las <span style=\"color:red\">ssumas</span> de k elementos de una lista de listas, de la misma longitud, con $k$ menor o igual que la longitud de cualquier lista de la lista.\n",
    "\n",
    "   - Para ello vamos a definir una función auxiliar <span style=\"color:red\">aux(k,r)</span> cuya salida sea una lista con todas las listas posibles de la forma $[l_0,l_2,\\ldots,l_{k-1}]$ con\n",
    "$0\\leq l_0 < l_2 <\\ldots< l_{k-1} \\leq r.$\n",
    "   \n",
    "   - La función  <span style=\"color:red\">suma(lista,k)</span>: La variable \"lista\" tiene que ser una lista de listas, todas ellas de la misma longitud, primero comprueba que $k\\leq $<span style=\"color:green\">len(lista)</span> y luego da una lista con todas las \n",
    "<span style=\"color:red\">ssumas</span> posibles de $k$ elementos de la \"lista\"\n",
    "   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def abmod(x,n):\n",
    "    #Definimos x1 como el resto de x dividido por n\n",
    "    x1=x%n\n",
    "    #Comprobamos si x1 es menor o igual que (n/2)\n",
    "    if x1<=(n/2):\n",
    "        #Si cumple la condición devolvemos x1\n",
    "        return x1\n",
    "    else:\n",
    "        #Si no la cumple devolvemos x1-n\n",
    "        return x1-n\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def mayorpot(p,m):\n",
    "    #Comprobamos si p es -1\n",
    "    if p==-1:\n",
    "        if m<0:\n",
    "            return 1\n",
    "        else:\n",
    "            return 0\n",
    "    #Quitamos casos triviales\n",
    "    if p==0:\n",
    "        return \"Es una trivialidad preguntarse cual es la mayor potencia de 0 que divide a m\"\n",
    "    if p==1:\n",
    "        return 1\n",
    "    #Comprobamos si p divide a m\n",
    "    if m%p!=0:\n",
    "        return 0\n",
    "    #Si p divide a m usamos de variable auxiliar a, con la cual iremos haciendo las potencias de p\n",
    "    #Y comprobar hasta que potencia se divide a m, usamos i como variable auxiliar para ver el exponente de la potencia\n",
    "    else:\n",
    "        i=1\n",
    "        a=p\n",
    "        while m%(a*p)==0:\n",
    "            i=i+1\n",
    "            a=a*p\n",
    "        #Devuelve el exponente de la mayor potencia que divide a m\n",
    "        return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "def bnumer(b,base,n):\n",
    "    #Hacemos la b^2 mod n con nuestra función abmod\n",
    "    #Llamamos b1 a ese número\n",
    "    b1=abmod(b**2,n)\n",
    "    #Hacemos la mayor potencia de los primos que divida a este número\n",
    "    #Y los vamos multiplicando en la variable prod\n",
    "    prod=1\n",
    "    for i in range(0,len(base)):\n",
    "        #Llamamos x a la mayor potencia\n",
    "        x=base[i]**mayorpot(base[i],b1)\n",
    "        prod=prod*x\n",
    "    #Comprobamos si el producto es el número b\n",
    "    if prod==b1:\n",
    "        return true\n",
    "    else:\n",
    "        return false\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "def vec_alfa(b,base,n):\n",
    "    #Comprueba si b es un b-numero\n",
    "    if bnumer(b,base,n)==false:\n",
    "        return\n",
    "    else:\n",
    "        #Definimos el vector alfa como los exponentes asociados al bnumero en la base\n",
    "        vecalfa=[]\n",
    "        #Definimos b1 como b^2 mod n con nuestra función abmod\n",
    "        b1=b1=abmod(b**2,n)\n",
    "        for i in range(0,len(base)):\n",
    "            vecalfa=vecalfa+[mayorpot(base[i],b1)]\n",
    "        return vecalfa"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def parp(lista):\n",
    "    #Devolvemos true si todos los elementos de la lista son pares, en otro caso false.\n",
    "    for i in range(0,len(lista)):\n",
    "        if lista[i]%2!=0:\n",
    "            return false\n",
    "    return true"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def ssuma(lista1,lista2):\n",
    "    #Sumamos elemento a elemento dos listas\n",
    "    if len(lista1)!=len(lista2):\n",
    "        print 'No tienen la misma dimensión las dos listas'\n",
    "        return\n",
    "    #Definimos la lista en la que vamos a sumar estas dos\n",
    "    listsuma=[]\n",
    "    for i in range(0,len(lista1)):\n",
    "        listsuma=listsuma+[lista1[i]+lista2[i]]\n",
    "    return listsuma\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "def aux(k,r):\n",
    "    #Lista con el número total de elementos r\n",
    "    lista=range(0,r)\n",
    "    #Lista de listas con las posibles combinaciones de elementos de lista tomados de k en k\n",
    "    aux=list(combinations(lista, k))\n",
    "    return aux\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [],
   "source": [
    "def ssuman(lista):\n",
    "    #Sumar n listas, que son los elementos de una lista.\n",
    "    suma=lista[0]\n",
    "    for i in range(1,len(lista)):\n",
    "        suma=ssuma(suma,lista[i])\n",
    "    return suma\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [],
   "source": [
    "def suma(lista,k):\n",
    "    r=len(lista)\n",
    "    #lista es una lista de listas\n",
    "    #comprobamos que la longitud de la lista sea mayor que k\n",
    "    if len(lista)<=k:\n",
    "        return\n",
    "    #definimos la salida de la función que es una lista con todas las ssumas de k en k\n",
    "    aux1=aux(k,r)\n",
    "    m=factorial(r)/(factorial(k)*factorial(r-k))\n",
    "    lista1=[[]]\n",
    "\n",
    "    for i in range(0,m):\n",
    "        if i>0:\n",
    "            lista1.append([])\n",
    "        for j in aux1[i]:\n",
    "            if j==aux1[i][0]:\n",
    "                lista1[i]=lista1[i]+lista[j]\n",
    "            elif j==aux1[i][1]:\n",
    "                lista1[i]=[lista1[i]]+[lista[j]]\n",
    "            else:\n",
    "                lista1[i]=lista1[i]+[lista[j]]\n",
    "    lista2=[]\n",
    "    for i in range(0,m):\n",
    "        lista2.append(ssuman(lista1[i]))\n",
    "    return lista2\n",
    "            \n",
    "    \n",
    "    \n",
    "    \n",
    "    \n",
    "        \n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Elección de la lista de $B$ números. Voy a seguir teniendo suerte"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Vamos a elegir una lista de $B$-números con la esperanza de que sean suficientes para resolver la ecuación #eq. El proceso será el siguiente:\n",
    "\n",
    " - Fijamos $k_{max}$ y también $i_{max}$. \n",
    " - Construimos la lista \n",
    " $$L_1=[n_k=\\mbox{ floor(sqrt($k*n$)), para } k=1,2,3,4,\\ldots,k_{max}].$$ \n",
    " - Construimos la lista $$L_2=[ b_{ki}=n_k + i, \\mbox{ para } n_k \\in L_1 \\mbox{ e } i=0,2,3,\\ldots,i_{max}-1]$$\n",
    " \n",
    " - Seleccionamos de $L_2$ aquellos $b_{ki}$ que son B-números y formamos la lista BN con ellos.\n",
    " \n",
    "Define una función <span style=\"color:red\">bi(n,k,i,base)</span> que realice el proceso de selección anterior."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [],
   "source": [
    "def bi(n,k,i,base):\n",
    "    #Definimos la lista L1\n",
    "    L1=[]\n",
    "    for l in range(1,k+1):\n",
    "        L1=L1+[floor(sqrt(l*n))]\n",
    "    #Definimos la lista L2\n",
    "    L2=[]\n",
    "    for l in range(0,len(L1)):\n",
    "        for j in range(0,i):\n",
    "            L2=L2+[L1[l]+j]\n",
    "    #Seleccionamos aquellos números de L2 que sean B-números\n",
    "    BN=[]\n",
    "    for l in range(0,len(L2)):\n",
    "        if bnumer(L2[l],base,n)==true:\n",
    "            BN=BN+[L2[l]]\n",
    "    return BN"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Algoritmo de resolución de la ecuación $x^2=y^2 \\mod n$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Imput n\n",
    "- output (t,s) con $t^2=s^2\\mod n$\n",
    "\n",
    "    - **paso 1.-** Elegimos una base $B$ y esperamos tener suerte.\n",
    "    - **paso 2.-** Elegimos índices $k_{max}$ e $i_{max}$ y construimos la lista de $B$-números <span style=\"color:green\">BN</span>= <span style=\"color:red\">bi(n,$k_{max}$,$i_{max}$,base)</span> y volvemos a esperar tener suerte.\n",
    "    - **paso 3.-** Construimos la lista <span style=\"color:green\">alfavec</span> de alfa vectores correspondientes a los $B$-números en $BN$.\n",
    "    - **paso 4.-** Inicializamos el índice $j=1$, construimos la lista <span style=\"color:green\">sumaj</span>=<span style=\"color:red\">suma(alfavec,j)</span> y nos quedamos con las sublista <span style=\"color:green\">sumajpar</span>  de sumaj cuyos elementos satisfagan la condición <span style=\"color:red\">parp</span>. Si <span style=\"color:green\">sumajpar</span> es vacía tomamos $j=j+1$ y repetimos el proceso anterior.\n",
    "    - **paso 5.-** Inicializamos $\\alpha$ como el primer elemento de <span style=\"color:green\">sumajpar</span>, tomamos $in_\\alpha$ como el lugar que ocupa $\\alpha$ en <span style=\"color:green\">sumaj</span>. Esto nos permite calcular la lista de eles para $\\alpha$,\n",
    "<center> <span style=\"color:green\">eles$\\alpha$</span> = <span style=\"color:red\">aux(len(B),j)[in_$\\alpha$]</span> = $[l_0,l_2,\\ldots,l_{j-1}]$</center>\n",
    "además tenemos que $$\\alpha=\\alpha_{l_0}+\\ldots +\\alpha_{l_{j-1}}.$$\n",
    "Si ponemos $\\alpha_{l_i}=(e_{l_i}^0,\\ldots,e_{l_i}^h)$ y $\\alpha=(e_0,\\ldots,e_h)$ entonces:\n",
    "$$ e_r=\\sum_{i=0}^{j-1} e_{l_i}^r$$\n",
    "    - **paso 6.-** Calculamos:\n",
    "    $$ t=\\prod_{i=0}^{j-1} b_{l_i} \\quad\\mbox{y}\\quad s=\\prod_{r=0}^h p_r^{\\frac{e_r}{2}}$$\n",
    "    - **paso 7.-** Si $(t,s)$ es una solución no trivial return $(t,s)$. En caso contrario volvemos al paso 5 tomando $\\alpha=$ siguiente de $\\alpha$.\n",
    "    - **Fin.-** Si todas las soluciones que hemos obtenido son triviales no hemos tenido suerte y cambiamos primero los índices $k_{max}$ e $i_{max}$ y si aún así no tenemos suerte cambiamos la base $B$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "** Ejercicio 1.-** Elije un entero $n$ positivo que empiece por los dígitos de tu DNI, asegúrate de que el $n$ que has elegido no es primo, y realiza el algoritmo anterior paso a paso.\n",
    "\n",
    "A partir de la solución que has obtenido, da una factorización de $n$.\n",
    "\n",
    "***Comprueba el resultado.***"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Paso 1. Elección de una base B"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Vamos a factorizar mi DNI que es 75908039, usando una base formada por -1 y los 20 primeros primos"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Elegimos como n el número que queremos factorizar, y una base B con los primeros h primos\n",
    "n=75908039\n",
    "h=20\n",
    "B=baseprim(h)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Paso 2.  Elegimos k e i, y hacemos una lista con los B-números"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Construimos la lista de los B-números, usando los valores de kmax=60 e imax=60\n",
    "k=60\n",
    "i=60\n",
    "BN=bi(n,k,i,B)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Paso 3. Construimos una lista con los alfa vectores"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Construimos la lista de los alfa vectores asociados a estos B-números\n",
    "alfavec=[]\n",
    "for i in range(0,len(BN)):\n",
    "    alfavec.append(vec_alfa(BN[i],B,n))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Paso 4. Buscamos la suma de alfavectores que nos dé una lista par"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Elegimos como j el número de alfa vectores que queremos sumar lo empezamos en 1 y lo podemos ir\n",
    "#subiendo hasta que consigamos una solución no trivial\n",
    "#j tiene que ser 1 o mayor\n",
    "#Para cada j guardamos todos las posibles sumas pares en una lista para comprobarlas luego 1 a 1\n",
    "sumajpar=[]\n",
    "in_a=[]\n",
    "j=1\n",
    "if j>=len(alfavec):\n",
    "    print'No se pueden sumar tantos elementos, prueba con otros k, i o base'\n",
    "else:\n",
    "    for i in range(0,len(alfavec)):\n",
    "        if parp(alfavec[i])==true:\n",
    "            sumajpar.append(alfavec[i])\n",
    "            in_a.append(i)\n",
    "    if sumajpar==[]:\n",
    "        while sumajpar==[]:\n",
    "            j=j+1\n",
    "            if j>=len(alfavec):\n",
    "                print'No se pueden sumar tantos elementos, prueba con otros k, i o base'\n",
    "                break\n",
    "            sumaj=suma(alfavec,j)\n",
    "            for i in range(0,len(sumaj)):\n",
    "                if parp(sumaj[i])==true:\n",
    "                    sumajpar.append(sumaj[i])\n",
    "                    in_a.append(i)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Paso 5. Nos quedamos con la posición de los alfavectores que se han sumado"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Distinguimos los casos en los que se hayan sumado varios alfavectores o sea solo 1\n",
    "#Guardamos en eles_a todas las posibles combinaciones de suma de alfavectores\n",
    "#Mientras que en in_a tenemos las posiciones para las cuales la suma da par\n",
    "if j==1:\n",
    "    eles_a=in_a\n",
    "    print eles_a\n",
    "else:\n",
    "    eles_a = aux(j,len(BN))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Paso 6. Calculamos t y s, y si la solución es no trivial  damos la factorización de n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "75908039  =  546101 * 139\n"
     ]
    }
   ],
   "source": [
    "#calculamos t y s para todas las posibilidades de sumas de alfavectores\n",
    "#usamos l como contador para movernos entre las posibles combinaciones de sumas\n",
    "#Si t y s es no trivial da una factorización de n\n",
    "#Si t y s es una solución trivial imprime que no hemos tenido suerte\n",
    "for l in range(1,len(in_a)):\n",
    "    t=1\n",
    "    if j==1:\n",
    "        t=(t*BN[eles_a[l]])%n\n",
    "    \n",
    "    else:\n",
    "        for i in range(0,len(eles_a[in_a[l]])):\n",
    "            t=(t*BN[eles_a[in_a[l]][i]])%n\n",
    "    p=[]\n",
    "    e=[]\n",
    "    for i in range (0,len(sumajpar[l])):\n",
    "        if sumajpar[l][i]!=0:\n",
    "            p.append(B[i])\n",
    "            e.append(sumajpar[l][i]/2)\n",
    "    s=1\n",
    "    for i in range(0,len(p)):\n",
    "        s=(s*pow(p[i],e[i],n))%n\n",
    "    #Comprobamos que sea una solución no trivial\n",
    "    if gcd(s+t,n)!=1 and gcd(s-t,n)!=1:\n",
    "        print n,' = ',n/gcd(s+t,n),'*',gcd(s+t,n)\n",
    "        break\n",
    "    if l ==len(in_a)-1:\n",
    "        print 'No hemos tenido suerte'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Y conseguimos finalmente factorizar mi DNI=75908039 como el producto de dos primos, 546101 y 139"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n"
     ]
    }
   ],
   "source": [
    "#Comprobamos que es factorización\n",
    "print 546101*139==75908039"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "** Ejercicio (Avanzado) 2.-** Define una función \n",
    "<center><span style=\"color:red\">soleq(n,h,k,i)</span></center>\n",
    "que haga lo siguiente:\n",
    "- Tome como Base Factor a la lista formada por $-1$ seguido de los $h$-primeros primos.\n",
    "- Tome $k$ e $i$ como los índices $k_{max}$ e $i_{max}$ en el algoritmo anterior\n",
    "- Tenga como salida:\n",
    "   - print todas las soluciones son triviales, o bien\n",
    "   - $(t,s)$,  una solución no trivial de la ecuación $x^2\\equiv y^2 \\mod n$.\n",
    "\n",
    "Comprueba que tu función \"funciona\" utilizando el $n$ del ejercicio anterior y viendo que obtienes los mismos resultados.\n",
    "\n",
    "Aplica la función <span style=\"color:red\">soleq</span> a varios ejemplos y comprueba los resultados.\n",
    "\n",
    "** Ejercicio (Avanzado) 3.-** Define una función \n",
    "<center><span style=\"color:red\">fac(n,h)</span></center>\n",
    "para factrorizar $n$ que utilice la función soleq. El parámetro $h$ indica el número de primos que van a formar parte de la base factor. He omitido los índices $k$ e $i$ pero puedes añadirlos si los necesitas."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Ejercicio 2: Una función para resolver la ecuación."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "#También devolvemos True o False para saber si hemos podido resolver la ecuación\n",
    "def soleq(n,h,k,i):\n",
    "    #Definimos n1 y bp como los valores de n y h\n",
    "    n1=n\n",
    "    bp=h\n",
    "    #Definimos la base con los primeros primos\n",
    "    B=baseprim(bp)\n",
    "    #NOs quedamos con los B-números\n",
    "    BN=bi(n1,k,i,B)\n",
    "    #Construimos la lista de los alfa vectores asociados a estos B-números\n",
    "    alfavec=[]\n",
    "    for i in range(0,len(BN)):\n",
    "        alfavec.append(vec_alfa(BN[i],B,n1))\n",
    "    #Elegimos como j el número de alfa vectores que queremos sumar lo empezamos en 1 y lo podemos ir\n",
    "    #subiendo hasta que consigamos una solución no trivial\n",
    "    #j tiene que ser 1 o mayor\n",
    "    #Cuando j es 1 vamos a mirar si hay alfavectores pares y luego comprobaremos uno a uno si dan soluciones\n",
    "    #Cuando j es mayor que 1 iremos comprobando 1 a 1 si dan solución.\n",
    "    #Usamos i_0 como contador para saber por qué valor de j vamos comprobando\n",
    "    #Usamos i_1 como contador para saber dentro de cada valor de j, por qué combinación de alfavectores pares vamos\n",
    "    i_0=1 \n",
    "    i_1=0\n",
    "    for j in range(i_0,len(alfavec)):\n",
    "        sumajpar=[]\n",
    "        in_a=[]\n",
    "        if j==1:\n",
    "            for i in range(0,len(alfavec)):\n",
    "                if parp(alfavec[i])==true:\n",
    "                    #Si encontramos un alfavector par, lo guardamos éste y su posición\n",
    "                    sumajpar.append(alfavec[i])\n",
    "                    in_a.append(i)\n",
    "            #Comprobamos con cada alfavector par\n",
    "            for l in range(0,len(in_a)):\n",
    "                eles_a=in_a\n",
    "                \n",
    "                #Calculamos t\n",
    "                t=1\n",
    "                t=(t*BN[eles_a[l]])%n\n",
    "                p=[]\n",
    "                e=[]\n",
    "                for i in range (0,len(sumajpar)):\n",
    "                    if sumajpar[l][i]!=0:\n",
    "                        p.append(B[i])\n",
    "                        e.append(sumajpar[l][i]/2)\n",
    "                #Calculamos s\n",
    "                s=1\n",
    "                for i in range(0,len(p)):\n",
    "                    s=(s*pow(p[i],e[i],n))%n\n",
    "        #Comprobamos que sea una solución no trivial\n",
    "                if gcd(s+t,n)!=1:\n",
    "                    return[true,(t,s)]\n",
    "        #Entramos en este if si no hay ningun alfavector par y tenemos que probar con sumas (j mayor que 1)\n",
    "        if sumajpar==[]:\n",
    "            in_a=0\n",
    "            while sumajpar==[]:\n",
    "                i_1=0\n",
    "                j=j+1\n",
    "                #Ponemos una condición de parada que es que j llegue a 15, \n",
    "                #o si el j es mayor que la longitud de alfavec, no podemos hacer las sumas\n",
    "                if j>=len(alfavec) or j==15:\n",
    "                    return [false,\"No hemos resuelto la ecuación\"]\n",
    "                #Lista con todas las sumas de j en j de alfavectores\n",
    "                sumaj=suma(alfavec,j)\n",
    "                for i in range(i_1,len(sumaj)):\n",
    "                    #Comprobamos una a una si la suma de alfavectores es par\n",
    "                     if parp(sumaj[i])==true:\n",
    "                        #Si es par procedemos a comprobar si da solución\n",
    "                        sumajpar=sumaj[i]\n",
    "                        in_a=i\n",
    "                        i_0=j\n",
    "                        i_1=i   \n",
    "    #Vemos cual es la combinación que se ha sumado para obtener el par\n",
    "                        eles_a =aux(j,len(BN))\n",
    "                        #Calculamos t \n",
    "                        t=1\n",
    "                        for i in range(0,len(eles_a[in_a])):\n",
    "                            t=(t*BN[eles_a[in_a][i]])%n\n",
    "                        p=[]\n",
    "                        e=[]\n",
    "                        for i in range (0,len(sumajpar)):\n",
    "                            if sumajpar[i]!=0:\n",
    "                                p.append(B[i])\n",
    "                                e.append(sumajpar[i]/2)\n",
    "                        #Calculamos s\n",
    "                        s=1\n",
    "                        for i in range(0,len(p)):\n",
    "                            s=(s*pow(int(p[i]),int(e[i]),int(n)))%n\n",
    "        #Comprobamos que sea una solución no trivial\n",
    "                        if gcd(s+t,n)!=1 and gcd(s-t,n)!=1:\n",
    "                            return[true,(t,s)]\n",
    "    return [false]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[True, (73161896, 25136284)]\n",
      "0\n",
      "True\n"
     ]
    }
   ],
   "source": [
    "#Probemos a resolver la ecuación con la función definida\n",
    "sol=soleq(75908039,30,30,30)\n",
    "print sol\n",
    "print (sol[1][0]**2-sol[1][1]**2)%75908039\n",
    "#Vemos que ha conseguido resolver la ecuación que se planteaba antes.\n",
    "#Vemos que no sea trivial\n",
    "print gcd(sol[1][0]-sol[1][1],75908039)!=1 and gcd(sol[1][0]+sol[1][1],75908039)!=1\n",
    "#Comprobamos que no es trivial"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[True, (2105, 8)]\n",
      "0\n",
      "True\n"
     ]
    }
   ],
   "source": [
    "#Probemos ahora con otro ejemplo\n",
    "sol2=soleq(492329,30,30,30)\n",
    "print sol2\n",
    "print (sol2[1][0]**2-sol2[1][1]**2)%492329\n",
    "#Volvemos a resolver la ecuación, comprobamos que sea no trivial\n",
    "print gcd(sol2[1][0]-sol2[1][1],492329)!=1 and gcd(sol2[1][0]+sol2[1][1],492329)!=1\n",
    "#Comprobamos que no es trivial"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Ejercicio 3: Una función para factorizar."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def fac(n,h):\n",
    "    n1=n\n",
    "    h1=h\n",
    "    i=5\n",
    "    k=5\n",
    "    factorizacion=true\n",
    "    sol=soleq(n1,h1,k,i)\n",
    "    if sol[0]==true:\n",
    "        s=sol[1][0]\n",
    "        t=sol[1][1]\n",
    "    else:\n",
    "        while sol[0]==false:\n",
    "            k=k+5\n",
    "            i=i+5\n",
    "            sol=soleq(n1,h1,k,i)\n",
    "            if sol[0]==true:\n",
    "                s=sol[1][0]\n",
    "                t=sol[1][1]\n",
    "            if i==100:\n",
    "                factorizacion=false\n",
    "                break\n",
    "    if factorizacion==false:\n",
    "        print 'Peligro de bucle infinito, elige otro h'\n",
    "    else: \n",
    "        return (gcd(s+t,n),n/gcd(s+t,n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(546101, 139)\n"
     ]
    }
   ],
   "source": [
    "#Probemos a volver a factorizar mi DNI con esta función\n",
    "print fac(75908039,20)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(93893, 839)\n",
      "True\n"
     ]
    }
   ],
   "source": [
    "#Probemos ahora a factorizar otro número como el producto de dos primos en este caso\n",
    "f=fac(78776227,20)\n",
    "print f\n",
    "#Comprobamos que factoriza\n",
    "print f[0]*f[1]==78776227"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Elección de la base. Fracciones continuas"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La función <span style=\"color:green\">continued_fraction_periodic(a,b,d)</span> calcula la fracción continua asociada a $\\frac{a+\\sqrt d}{b}$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 32,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[95, [3, 1, 26, 2, 6, 1, 1, 3, 2, 1, 5, 3, 1, 7, 5, 1, 1, 1, 4, 4, 4, 1, 1, 1, 5, 7, 1, 3, 5, 1, 2, 3, 1, 1, 6, 2, 26, 1, 3, 190]]\n"
     ]
    }
   ],
   "source": [
    "F=continued_fraction_periodic(0,1,9073) # (0+sqrt(9073))/1\n",
    "print F"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "la función <span style=\"color:green\">continued_fraction_convergents(lista)</span> calcula los convergentes"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 33,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[95, 3, 1, 26, 2, 6]\n"
     ]
    }
   ],
   "source": [
    "L1=[F[0]]+F[1][:5]\n",
    "print L1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {},
   "outputs": [],
   "source": [
    "L2=continued_fraction_convergents(L1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[95, 286/3, 381/4, 10192/107, 20765/218, 134782/1415]\n"
     ]
    }
   ],
   "source": [
    "L3=list(L2)\n",
    "print L3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "286/3"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "L3[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "286"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "fraction(L3[1])[0]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Algoritmo de elección de la Base factor y de los B-números"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- **Paso 1.-** Calculamos la fracción continua asociada a $\\sqrt n$\n",
    "<center> F = <span style=\"color:green\">continued_fraction_periodic(0,1,n).</span></center>\n",
    "- **Paso 2.-** Formamos la lista\n",
    "<center> $L_1 =$ <span style=\"color:green\">F[0]+F[1].</span></center>\n",
    "- **Paso 3.-** Elegimos $s\\leq len(L_1)$, calculamos los convergentes \n",
    "<center> $L_2 = $<span style=\"color:green\">continued_fraction_convergents($L_1$[:s]).</span></center>\n",
    "- **Paso 4.-** Formamos la lista Pbs cuyos elementos son los numeradores de los elementos en $L_2$.\n",
    "- **Paso 5.-** Para cada $b\\in Pbs$ factorizamos <span style=\"color:green\">abmod $(b^2,n)$.</span>\n",
    "- **Paso 6.-** La base factor $B$ estará formada por $-1$ junto con los primos que:\n",
    "   - aparecen en la factorización de <span style=\"color:green\">abmod $(b^2,n)$</span> para al menos dos b's en Pbs, o bien\n",
    "   - aparece con un exponente par en la factorización de <span style=\"color:green\">abmod $(b^2,n)$</span> para exactamente un b.\n",
    "-  **Paso 7.-** La lista de B-números estará formada por aquellos b's en Pbs que sean B-números para la base obtenida en el paso anterior."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "** Ejercicio 4.-** Elije un entero $n$ positivo que empiece por los dígitos de tu DNI, asegúrate de que el $n$ que has elegido no es primo y que es distinto del que elegiste en el ejercicio 1, y realiza el algoritmo anterior paso a paso obteniendo una base $B$ y una lista de $B$-números $BN$.\n",
    "\n",
    "** Ejercicio 5.-** Completa el ejercicio 3 resolviendo la ecuación $x^2\\equiv y^2\\mod n$ utilizando como base factor y lista de B-números los obtenidos en el ejercicio 3. \n",
    "\n",
    "** Ejercicio 5.-** Completa el ejercicio 4 factorizando el $n$ que has elegido.\n",
    "\n",
    "** Ejercicio (Avanzado) 6.-** Automatiza los procesos de elección de base factor y resolución de la ecuación, para ello define una función  <span style=\"color:red\">soleqfc(n,s)</span>.\n",
    "\n",
    "** Ejercicio (Avanzado) 7.-** Define una función <span style=\"color:red\">facfc(n)</span> que factorice $n$ utilizando la función soleqfc.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Paso 1: Calculamos la fracción continua asociada a $\\sqrt n$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Para este algoritmo vamos a factorizar mi DNI con un 1 al final, 759080391\n",
    "n=759080391\n",
    "F = continued_fraction_periodic(0,1,n)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Paso 2:  Formamos la lista $L_{1}=F[0]+F[1]$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {},
   "outputs": [],
   "source": [
    "L1= [F[0]]+F[1]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Paso 3: Elegimos $s\\leq len(L_1)$, calculamos los convergentes "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[27551, 55103/2, 137757/5, 330617/12, 468374/17, 798991/29, 4463329/162, 9725649/353, 14188978/515, 38103605/1383, 128499793/4664, 295103191/10711, 423602984/15375, 718706175/26086, 5454546209/197977, 6173252384/224063, 11627798593/422040, 99195641128/3600383, 110823439721/4022423, 320842520570/11645229, 431665960291/15667652, 1184174441152/42980533, 7536712607203/273550850, 23794312262761/863633083, 31331024869964/1137183933, 86456362002689/3138000949, 290700110878031/10551186780, 2121357138148906/76996308409, 19382914354218185/703517962461, 176567586326112571/6408657970558]\n"
     ]
    }
   ],
   "source": [
    "s=30\n",
    "if s<=len(L1):\n",
    "    L2=list(continued_fraction_convergents(L1[:s]))\n",
    "print L2\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Paso 4: Formamos la lista Pbs cuyos elementos son los numeradores de los elementos en $L_2$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[27551, 55103, 137757, 330617, 468374, 798991, 4463329, 9725649, 14188978, 38103605, 128499793, 295103191, 423602984, 718706175, 5454546209, 6173252384, 11627798593, 99195641128, 110823439721, 320842520570, 431665960291, 1184174441152, 7536712607203, 23794312262761, 31331024869964, 86456362002689, 290700110878031, 2121357138148906, 19382914354218185, 176567586326112571]\n"
     ]
    }
   ],
   "source": [
    "Pbs=[]\n",
    "for i in range(0,len(L2)):\n",
    "    Pbs.append(fraction(L2[i])[0])\n",
    "print Pbs "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Paso 5 y 6:  Para cada $b\\in Pbs$ factorizamos <span style=\"color:green\">abmod $(b^2,n)$</span>. La base factor $B$ estará formada por $-1$ junto con los primos que:  aparecen en la factorización de <span style=\"color:green\">abmod $(b^2,n)$</span> para al menos dos b's en Pbs, o bien"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Esta función asignará la base según los Pbs\n",
    "def elecbase(Pbs):\n",
    "#Lista de los Pbs\n",
    "    Pbs1=Pbs\n",
    "#Ceamos una lista donde guardar la factorización de todos los b números\n",
    "    factorb=[]\n",
    "#Inicializamos nuestra lista B\n",
    "    B=[-1]\n",
    "#Lista que usaremos de apoyo para construir la B, guardaremos en ella los números que no se repitan\n",
    "#en las factorizaciones, junto al número de los Pbs del cual es factor.\n",
    "    Baux=[]\n",
    "#Guardamos las factorizaciones de los números en factorb, junto a la posición del número\n",
    "#al cual corresponde la factorización en Pbs\n",
    "    for i in range(0,len(Pbs1)):\n",
    "        factorb.append([list(factorint(Pbs1[i])),i])\n",
    "    \n",
    "#Bucles anidados en los cuales compararemos los factores de los números de Pbs para guardar directamente\n",
    "#en B los que se repitan dos o más veces y los que salga sólo una vez los guardaremos en Baux\n",
    "#Para comprobar a continuación si tienen exponente par en la factorización del número del cual es factor\n",
    "#usamos a como variable booleana para comprobar que no metemos dos veces el mismo valor en B\n",
    "#b también será una variable booleana y esta llevará os indicará cuando un número sólo sale una vez\n",
    "\n",
    "    for i in range(0,len(factorb)):\n",
    "        for j in range(0,len(factorb[i][0])):\n",
    "            b=false\n",
    "            for k in range(i+1,len(factorb)):\n",
    "                for l in range(0,len(factorb[k][0])):\n",
    "                    a=false\n",
    "                    if factorb[i][0][j]==factorb[k][0][l]:\n",
    "                        b=true\n",
    "                        for m in range(0,len(B)):\n",
    "                            if(factorb[i][0][j]==B[m]):\n",
    "                                a=true\n",
    "                        if a==false:\n",
    "                             B.append(factorb[i][0][j])\n",
    "            \n",
    "            for m in range(0,len(B)):\n",
    "                if(factorb[i][0][j]==B[m]):\n",
    "                    b=true\n",
    "            if b==false:\n",
    "                Baux.append([factorb[i][0][j],i])\n",
    "\n",
    "#Comprobamos si tienen exponente par los almacenados en Baux para añadirlos a B             \n",
    "    for i in range(0,len(Baux)):\n",
    "        if mayorpot(Baux[i][0],Pbs1[Baux[i][1]])%2==0:\n",
    "            B.append(Baux[i][0])\n",
    "    \n",
    "    return B\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[-1, 3, 47, 7, 2, 13, 5, 19, 11]"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "elecbase(Pbs)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "#Función para ordenar una lista\n",
    "def orden(list):\n",
    "    for i in range(1,len(list)):\n",
    "        for j in range(0,len(list)-1):\n",
    "            if(list[j] > list[j+1]):\n",
    "                k = list[j+1]\n",
    "                list[j+1] = list[j]\n",
    "                list[j] = k;\n",
    "    return list"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [],
   "source": [
    "#Asignamos en B nuestra base, y la ordenamos\n",
    "B=elecbase(Pbs)\n",
    "B=orden(B)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Paso 8: La lista de B-números estará formada por aquellos b's en Pbs que sean B-números para la base obtenida en el paso anterior."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[-1, 2, 3, 5, 7, 11, 13, 19, 47]\n",
      "[47721, 95442, 143163, 190884]\n"
     ]
    }
   ],
   "source": [
    "print B\n",
    "k=60\n",
    "i=10\n",
    "#Construimos la lista de los B-números\n",
    "BN=bi(n,k,i,B)\n",
    "print BN"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Paso 9: Resolvemos el problemas con los Base y los B-números elegidos de esta forma."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[0, 2, 2, 0, 1, 1, 0, 1, 0], [0, 4, 2, 0, 1, 1, 0, 1, 0], [0, 2, 4, 0, 1, 1, 0, 1, 0], [0, 6, 2, 0, 1, 1, 0, 1, 0]]\n"
     ]
    }
   ],
   "source": [
    "#Construimos la lista de los alfa vectores asociados a estos B-números\n",
    "alfavec=[]\n",
    "for i in range(0,len(BN)):\n",
    "    alfavec.append(vec_alfa(BN[i],B,n))\n",
    "print alfavec"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[0, 6, 4, 0, 2, 2, 0, 2, 0], [0, 4, 6, 0, 2, 2, 0, 2, 0], [0, 8, 4, 0, 2, 2, 0, 2, 0], [0, 6, 6, 0, 2, 2, 0, 2, 0], [0, 10, 4, 0, 2, 2, 0, 2, 0], [0, 8, 6, 0, 2, 2, 0, 2, 0]]\n"
     ]
    }
   ],
   "source": [
    "#Elegimos como j el número de alfa vectores que queremos sumar lo empezamos en 1 y lo podemos ir\n",
    "#subiendo hasta que consigamos una solución no trivial\n",
    "#j tiene que ser 1 o mayor\n",
    "#Para cada j guardamos todos las posibles sumas pares en una lista para comprobarlas luego 1 a 1\n",
    "sumajpar=[]\n",
    "in_a=[]\n",
    "j=1\n",
    "if j>=len(alfavec):\n",
    "    print'No se pueden sumar tantos elementos'\n",
    "else:\n",
    "    for i in range(0,len(alfavec)):\n",
    "        if parp(alfavec[i])==true:\n",
    "            sumajpar.append(alfavec[i])\n",
    "            in_a.append(i)\n",
    "    if sumajpar==[]:\n",
    "        while sumajpar==[]:\n",
    "            j=j+1\n",
    "            if j>=len(alfavec):\n",
    "                print'No se pueden sumar tantos elementos'\n",
    "                break\n",
    "            sumaj=suma(alfavec,j)\n",
    "            for i in range(0,len(sumaj)):\n",
    "                if parp(sumaj[i])==true:\n",
    "                    sumajpar.append(sumaj[i])\n",
    "                    in_a.append(i)\n",
    "print sumajpar"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[0, 1, 2, 3, 4, 5] [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]\n"
     ]
    }
   ],
   "source": [
    "#Distinguimos los casos en los que se hayan sumado varios alfavectores o sea solo 1\n",
    "if j==1:\n",
    "    eles_a=in_a\n",
    "    print eles_a\n",
    "else:\n",
    "    eles_a = aux(j,len(BN))\n",
    "    print in_a,eles_a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 50,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "759080391  =  253026797 * 3\n"
     ]
    }
   ],
   "source": [
    "#calculamos t y s para todas las posibilidades de sumas de alfavectores\n",
    "#usamos l como contador para movernos entre las posibles combinaciones de sumas\n",
    "#Si t y s es no trivial da una factorización de n\n",
    "#Si t y s es una solución trivial imprime que no hemos tenido suerte\n",
    "for l in range(1,len(in_a)):\n",
    "    t=1\n",
    "    if j==1:\n",
    "        t=(t*BN[eles_a[l]])%n\n",
    "    \n",
    "    else:\n",
    "        for i in range(0,len(eles_a[in_a[l]])):\n",
    "            t=(t*BN[eles_a[in_a[l]][i]])%n\n",
    "    p=[]\n",
    "    e=[]\n",
    "    for i in range (0,len(sumajpar[l])):\n",
    "        if sumajpar[l][i]!=0:\n",
    "            p.append(B[i])\n",
    "            e.append(sumajpar[l][i]/2)\n",
    "    s=1\n",
    "    for i in range(0,len(p)):\n",
    "        s=(s*pow(p[i],e[i],n))%n\n",
    "    #Comprobamos que sea una solución no trivial\n",
    "    if gcd(s+t,n)!=1:\n",
    "        print n,' = ',n/gcd(s+t,n),'*',gcd(s+t,n)\n",
    "        break\n",
    "    if l ==len(in_a)-1:\n",
    "        print 'No hemos conseguido factorizar el número'"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 51,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "True\n"
     ]
    }
   ],
   "source": [
    "#Comprobamos efectivamente que es una factorización del número\n",
    "print 759080391==253026797*3"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Ejercicio 6: Función soleqfc."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def soleqfc(n,s):\n",
    "    #Definimos n1 y bp como los valores de n y h\n",
    "    n1=n\n",
    "    F = continued_fraction_periodic(0,1,n)\n",
    "    L1= [F[0]]+F[1]\n",
    "    if s<=len(L1):\n",
    "        L2=list(continued_fraction_convergents(L1[:s]))\n",
    "    elif s>len(L1):\n",
    "        return [false,\"No se ha podido factorizar el numero con este s, tienes que elegir un s mas pequeño\"]\n",
    "\n",
    "    Pbs=[]\n",
    "    for i in range(0,len(L2)):\n",
    "        Pbs.append(fraction(L2[i])[0])\n",
    "    B=elecbase(Pbs)\n",
    "    B=orden(B)\n",
    "    #Elegimos el k y el i y ponemos una condición para terminar el programa\n",
    "    sol=false\n",
    "    k1=0\n",
    "    i1=0\n",
    "    while sol==false:\n",
    "        #En cada iteración vamos aumentando los valores de k y de i\n",
    "        k1=k1+10\n",
    "        i1=i1+10\n",
    "        #Nos quedamos con los B-números\n",
    "        BN=bi(n1,k1,i1,B)\n",
    "        #Construimos la lista de los alfa vectores asociados a estos B-números\n",
    "        alfavec=[]\n",
    "        for i in range(0,len(BN)):\n",
    "            alfavec.append(vec_alfa(BN[i],B,n1))\n",
    "        #Hacemos un algoritmo análogo al de la función soleq\n",
    "        i_0=1 \n",
    "        i_1=0\n",
    "        for j in range(i_0,len(alfavec)):\n",
    "            sumajpar=[]\n",
    "            in_a=[]\n",
    "            if j==1:\n",
    "                #Comprobamos si hay alfavectores pares\n",
    "                for i in range(0,len(alfavec)):\n",
    "                    if parp(alfavec[i])==true:\n",
    "                        sumajpar.append(alfavec[i])\n",
    "                        in_a.append(i)\n",
    "                #Comprobamos si los alfavectores pares dan solución \n",
    "                for l in range(0,len(in_a)):\n",
    "                    eles_a=in_a\n",
    "                    #Calculamos t\n",
    "                    t=1\n",
    "                    t=(t*BN[eles_a[l]])%n\n",
    "                    p=[]\n",
    "                    e=[]\n",
    "                    for i in range (0,len(sumajpar)):\n",
    "                        if sumajpar[l][i]!=0:\n",
    "                            p.append(B[i])\n",
    "                            e.append(sumajpar[l][i]/2)\n",
    "                    #Calculamos s\n",
    "                    s=1\n",
    "                    for i in range(0,len(p)):\n",
    "                        s=(s*pow(p[i],e[i],n))%n\n",
    "        #Comprobamos que sea una solución no trivial\n",
    "                    if gcd(s+t,n)!=1:\n",
    "                        return[true,(t,s)]\n",
    "            #Comprobamos si hay sumas pares de alfavectores\n",
    "            if sumajpar==[]:\n",
    "                in_a=0\n",
    "                while sumajpar==[]:\n",
    "                    i_1=0\n",
    "                    j=j+1\n",
    "                    if j>=len(alfavec) or j==15:\n",
    "                        break\n",
    "                    #Condición para no hacer un bucle infinito\n",
    "                    elif k==100:\n",
    "                        return [false]\n",
    "                    sumaj=suma(alfavec,j)\n",
    "                    for i in range(i_1,len(sumaj)):\n",
    "                        if parp(sumaj[i])==true:\n",
    "                            sumajpar=sumaj[i]\n",
    "                            in_a=i\n",
    "                            i_0=j\n",
    "                            i_1=i   \n",
    "                        #Vemos que combinación da lugar al vector par\n",
    "                            eles_a =aux(j,len(BN))\n",
    "                        #calculamos t\n",
    "                            t=1\n",
    "                            for i in range(0,len(eles_a[in_a])):\n",
    "                                t=(t*BN[eles_a[in_a][i]])%n\n",
    "                            p=[]\n",
    "                            e=[]\n",
    "                            for i in range (0,len(sumajpar)):\n",
    "                                if sumajpar[i]!=0:\n",
    "                                    p.append(B[i])\n",
    "                                    e.append(sumajpar[i]/2)\n",
    "                            #Calculamos s\n",
    "                            s=1\n",
    "                            for i in range(0,len(p)):\n",
    "                                s=(s*pow(int(p[i]),int(e[i]),int(n)))%n\n",
    "        #Comprobamos que sea una solución no trivial\n",
    "                            if gcd(s+t,n)!=1 and gcd(s-t,n)!=1:\n",
    "                                return[true,(t,s)]\n",
    "    return [false]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[True, (105336, 105336)]\n",
      "True\n",
      "True\n"
     ]
    }
   ],
   "source": [
    "#Vemos que resuelve la ecuación asociada al número que elegimos para hacer el algoritmo paso a paso\n",
    "sol3=soleqfc(759080391,31)\n",
    "print sol3\n",
    "#Resuelve la ecuación\n",
    "print (sol3[1][0]**2)%759080391-(sol3[1][1]**2)%759080391==0\n",
    "#¿Es trivial la solución?\n",
    "print gcd(sol3[1][0]-sol3[1][1],759080391)!=1 and gcd(sol3[1][0]+sol3[1][1],759080391)!=1\n",
    "#No es trivial ya que ambos gcd son distintos de 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 54,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[True, (122304894, 98160982)]\n",
      "True\n",
      "True\n"
     ]
    }
   ],
   "source": [
    "#Probamos con otro número\n",
    "sol4=soleqfc(170168149,30)\n",
    "print sol4\n",
    "#Resuelve la ecuación\n",
    "print (sol4[1][0]**2)%170168149-(sol4[1][1]**2)%170168149==0\n",
    "#¿Es trivial la solución?\n",
    "print gcd(sol4[1][0]-sol4[1][1],170168149)!=1 and gcd(sol4[1][0]+sol4[1][1],170168149)!=1\n",
    "#No es trivial ya que ambos gcd son distintos de 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Ejercicio 7: Función para factorizar"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {},
   "outputs": [],
   "source": [
    "def facfc(n):\n",
    "    n1=n\n",
    "    #Damos un valor de s y un valor máximo de s por defecto, se podrá modificar según el problema al que nos enfrentemos\n",
    "    s=6\n",
    "    #Comprobamos si conseguimos factorizar el número para el s dado\n",
    "    sol=soleqfc(n1,s)\n",
    "    print sol\n",
    "    if sol[0]==true:\n",
    "        print\"1\"\n",
    "        q=sol[1][0]\n",
    "        t=sol[1][1]\n",
    "    else:\n",
    "        print \"5\"\n",
    "        while sol[0]==false:\n",
    "            print\"2\"\n",
    "        #Vamos ejecutando el método para cada valor de s hasta conseguir solución\n",
    "            sol=soleqfc(n1,s)\n",
    "            if sol[0]==true:\n",
    "                print \"3\"\n",
    "                q=sol[1][0]\n",
    "                t=sol[1][1]\n",
    "            #Aumentamos el número s\n",
    "            s=s+3\n",
    "            #Condición sobre un s máximo para no hacer un bucle infinito\n",
    "            if s>45:\n",
    "                return \"No hemos podido factorizar el numero\"\n",
    "    print \"4\"\n",
    "    #Devolvemos la factorización\n",
    "    return (gcd(q+t,n),n/gcd(q+t,n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {},
   "outputs": [
    {
     "ename": "KeyboardInterrupt",
     "evalue": "",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1;31mKeyboardInterrupt\u001b[0m                         Traceback (most recent call last)",
      "\u001b[1;32m<ipython-input-56-6b8be1d5a3d0>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m()\u001b[0m\n\u001b[0;32m      1\u001b[0m \u001b[1;31m#Probamos a factorizar el número que hemos usado paso a paso\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m----> 2\u001b[1;33m \u001b[0mf\u001b[0m\u001b[1;33m=\u001b[0m\u001b[0mfacfc\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;36m759080391\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m      3\u001b[0m \u001b[1;32mprint\u001b[0m \u001b[0mf\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m      4\u001b[0m \u001b[1;32mprint\u001b[0m \u001b[0mf\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;36m0\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m*\u001b[0m\u001b[0mf\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m==\u001b[0m\u001b[1;36m759080391\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;32m<ipython-input-55-534a59d92b3b>\u001b[0m in \u001b[0;36mfacfc\u001b[1;34m(n)\u001b[0m\n\u001b[0;32m      4\u001b[0m     \u001b[0ms\u001b[0m\u001b[1;33m=\u001b[0m\u001b[1;36m6\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m      5\u001b[0m     \u001b[1;31m#Comprobamos si conseguimos factorizar el número para el s dado\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m----> 6\u001b[1;33m     \u001b[0msol\u001b[0m\u001b[1;33m=\u001b[0m\u001b[0msoleqfc\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mn1\u001b[0m\u001b[1;33m,\u001b[0m\u001b[0ms\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m      7\u001b[0m     \u001b[1;32mprint\u001b[0m \u001b[0msol\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m      8\u001b[0m     \u001b[1;32mif\u001b[0m \u001b[0msol\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;36m0\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m==\u001b[0m\u001b[0mtrue\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;32m<ipython-input-52-5719fbbdc32d>\u001b[0m in \u001b[0;36msoleqfc\u001b[1;34m(n, s)\u001b[0m\n\u001b[0;32m     23\u001b[0m         \u001b[0mi1\u001b[0m\u001b[1;33m=\u001b[0m\u001b[0mi1\u001b[0m\u001b[1;33m+\u001b[0m\u001b[1;36m10\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     24\u001b[0m         \u001b[1;31m#Nos quedamos con los B-números\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m---> 25\u001b[1;33m         \u001b[0mBN\u001b[0m\u001b[1;33m=\u001b[0m\u001b[0mbi\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mn1\u001b[0m\u001b[1;33m,\u001b[0m\u001b[0mk1\u001b[0m\u001b[1;33m,\u001b[0m\u001b[0mi1\u001b[0m\u001b[1;33m,\u001b[0m\u001b[0mB\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m     26\u001b[0m         \u001b[1;31m#Construimos la lista de los alfa vectores asociados a estos B-números\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     27\u001b[0m         \u001b[0malfavec\u001b[0m\u001b[1;33m=\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;32m<ipython-input-18-052d6c09f4f5>\u001b[0m in \u001b[0;36mbi\u001b[1;34m(n, k, i, base)\u001b[0m\n\u001b[0;32m      8\u001b[0m     \u001b[1;32mfor\u001b[0m \u001b[0ml\u001b[0m \u001b[1;32min\u001b[0m \u001b[0mrange\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;36m0\u001b[0m\u001b[1;33m,\u001b[0m\u001b[0mlen\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mL1\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m      9\u001b[0m         \u001b[1;32mfor\u001b[0m \u001b[0mj\u001b[0m \u001b[1;32min\u001b[0m \u001b[0mrange\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;36m0\u001b[0m\u001b[1;33m,\u001b[0m\u001b[0mi\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m---> 10\u001b[1;33m             \u001b[0mL2\u001b[0m\u001b[1;33m=\u001b[0m\u001b[0mL2\u001b[0m\u001b[1;33m+\u001b[0m\u001b[1;33m[\u001b[0m\u001b[0mL1\u001b[0m\u001b[1;33m[\u001b[0m\u001b[0ml\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m+\u001b[0m\u001b[0mj\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m     11\u001b[0m     \u001b[1;31m#Seleccionamos aquellos números de L2 que sean B-números\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     12\u001b[0m     \u001b[0mBN\u001b[0m\u001b[1;33m=\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;32mC:\\Users\\Mik\\Anaconda2\\lib\\site-packages\\sympy\\core\\numbers.pyc\u001b[0m in \u001b[0;36m__add__\u001b[1;34m(self, other)\u001b[0m\n\u001b[0;32m   1783\u001b[0m     \u001b[1;31m# TODO make it decorator + bytecodehacks?\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m   1784\u001b[0m     \u001b[1;32mdef\u001b[0m \u001b[0m__add__\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mself\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mother\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m-> 1785\u001b[1;33m         \u001b[1;32mif\u001b[0m \u001b[0misinstance\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mother\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0minteger_types\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m   1786\u001b[0m             \u001b[1;32mreturn\u001b[0m \u001b[0mInteger\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mself\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mp\u001b[0m \u001b[1;33m+\u001b[0m \u001b[0mother\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m   1787\u001b[0m         \u001b[1;32melif\u001b[0m \u001b[0misinstance\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mother\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mInteger\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;31mKeyboardInterrupt\u001b[0m: "
     ]
    }
   ],
   "source": [
    "#Probamos a factorizar el número que hemos usado paso a paso\n",
    "f=facfc(759080391)\n",
    "print f\n",
    "print f[0]*f[1]==759080391"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {},
   "outputs": [
    {
     "ename": "KeyboardInterrupt",
     "evalue": "",
     "output_type": "error",
     "traceback": [
      "\u001b[1;31m---------------------------------------------------------------------------\u001b[0m",
      "\u001b[1;31mKeyboardInterrupt\u001b[0m                         Traceback (most recent call last)",
      "\u001b[1;32m<ipython-input-57-3cf94a2a65ef>\u001b[0m in \u001b[0;36m<module>\u001b[1;34m()\u001b[0m\n\u001b[0;32m      1\u001b[0m \u001b[1;31m#Probamos a factorizar otro número\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m----> 2\u001b[1;33m \u001b[0mf\u001b[0m\u001b[1;33m=\u001b[0m\u001b[0mfacfc\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;36m170168149\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m      3\u001b[0m \u001b[1;32mprint\u001b[0m \u001b[0mf\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m      4\u001b[0m \u001b[1;31m#Vemos que la factorización que ha salido es buena\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m      5\u001b[0m \u001b[1;32mprint\u001b[0m \u001b[1;36m170168149\u001b[0m\u001b[1;33m==\u001b[0m\u001b[0mf\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;36m0\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m*\u001b[0m\u001b[0mf\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;36m1\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;32m<ipython-input-55-534a59d92b3b>\u001b[0m in \u001b[0;36mfacfc\u001b[1;34m(n)\u001b[0m\n\u001b[0;32m      4\u001b[0m     \u001b[0ms\u001b[0m\u001b[1;33m=\u001b[0m\u001b[1;36m6\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m      5\u001b[0m     \u001b[1;31m#Comprobamos si conseguimos factorizar el número para el s dado\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m----> 6\u001b[1;33m     \u001b[0msol\u001b[0m\u001b[1;33m=\u001b[0m\u001b[0msoleqfc\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mn1\u001b[0m\u001b[1;33m,\u001b[0m\u001b[0ms\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m      7\u001b[0m     \u001b[1;32mprint\u001b[0m \u001b[0msol\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m      8\u001b[0m     \u001b[1;32mif\u001b[0m \u001b[0msol\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;36m0\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m==\u001b[0m\u001b[0mtrue\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;32m<ipython-input-52-5719fbbdc32d>\u001b[0m in \u001b[0;36msoleqfc\u001b[1;34m(n, s)\u001b[0m\n\u001b[0;32m     23\u001b[0m         \u001b[0mi1\u001b[0m\u001b[1;33m=\u001b[0m\u001b[0mi1\u001b[0m\u001b[1;33m+\u001b[0m\u001b[1;36m10\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     24\u001b[0m         \u001b[1;31m#Nos quedamos con los B-números\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m---> 25\u001b[1;33m         \u001b[0mBN\u001b[0m\u001b[1;33m=\u001b[0m\u001b[0mbi\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mn1\u001b[0m\u001b[1;33m,\u001b[0m\u001b[0mk1\u001b[0m\u001b[1;33m,\u001b[0m\u001b[0mi1\u001b[0m\u001b[1;33m,\u001b[0m\u001b[0mB\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m     26\u001b[0m         \u001b[1;31m#Construimos la lista de los alfa vectores asociados a estos B-números\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     27\u001b[0m         \u001b[0malfavec\u001b[0m\u001b[1;33m=\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;32m<ipython-input-18-052d6c09f4f5>\u001b[0m in \u001b[0;36mbi\u001b[1;34m(n, k, i, base)\u001b[0m\n\u001b[0;32m     12\u001b[0m     \u001b[0mBN\u001b[0m\u001b[1;33m=\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     13\u001b[0m     \u001b[1;32mfor\u001b[0m \u001b[0ml\u001b[0m \u001b[1;32min\u001b[0m \u001b[0mrange\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;36m0\u001b[0m\u001b[1;33m,\u001b[0m\u001b[0mlen\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mL2\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m---> 14\u001b[1;33m         \u001b[1;32mif\u001b[0m \u001b[0mbnumer\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mL2\u001b[0m\u001b[1;33m[\u001b[0m\u001b[0ml\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m,\u001b[0m\u001b[0mbase\u001b[0m\u001b[1;33m,\u001b[0m\u001b[0mn\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m==\u001b[0m\u001b[0mtrue\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m     15\u001b[0m             \u001b[0mBN\u001b[0m\u001b[1;33m=\u001b[0m\u001b[0mBN\u001b[0m\u001b[1;33m+\u001b[0m\u001b[1;33m[\u001b[0m\u001b[0mL2\u001b[0m\u001b[1;33m[\u001b[0m\u001b[0ml\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     16\u001b[0m     \u001b[1;32mreturn\u001b[0m \u001b[0mBN\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;32m<ipython-input-11-4684cd834216>\u001b[0m in \u001b[0;36mbnumer\u001b[1;34m(b, base, n)\u001b[0m\n\u001b[0;32m      2\u001b[0m     \u001b[1;31m#Hacemos la b^2 mod n con nuestra función abmod\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m      3\u001b[0m     \u001b[1;31m#Llamamos b1 a ese número\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m----> 4\u001b[1;33m     \u001b[0mb1\u001b[0m\u001b[1;33m=\u001b[0m\u001b[0mabmod\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mb\u001b[0m\u001b[1;33m**\u001b[0m\u001b[1;36m2\u001b[0m\u001b[1;33m,\u001b[0m\u001b[0mn\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m      5\u001b[0m     \u001b[1;31m#Hacemos la mayor potencia de los primos que divida a este número\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m      6\u001b[0m     \u001b[1;31m#Y los vamos multiplicando en la variable prod\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;32mC:\\Users\\Mik\\Anaconda2\\lib\\site-packages\\sympy\\core\\decorators.pyc\u001b[0m in \u001b[0;36m__sympifyit_wrapper\u001b[1;34m(a, b)\u001b[0m\n\u001b[0;32m     75\u001b[0m                 \u001b[1;32mif\u001b[0m \u001b[1;32mnot\u001b[0m \u001b[0mhasattr\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mb\u001b[0m\u001b[1;33m,\u001b[0m \u001b[1;34m'_op_priority'\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     76\u001b[0m                     \u001b[0mb\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0msympify\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mb\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mstrict\u001b[0m\u001b[1;33m=\u001b[0m\u001b[0mTrue\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m---> 77\u001b[1;33m                 \u001b[1;32mreturn\u001b[0m \u001b[0mfunc\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0ma\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mb\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m     78\u001b[0m             \u001b[1;32mexcept\u001b[0m \u001b[0mSympifyError\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     79\u001b[0m                 \u001b[1;32mreturn\u001b[0m \u001b[0mretval\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;32mC:\\Users\\Mik\\Anaconda2\\lib\\site-packages\\sympy\\core\\decorators.pyc\u001b[0m in \u001b[0;36mbinary_op_wrapper\u001b[1;34m(self, other)\u001b[0m\n\u001b[0;32m    116\u001b[0m                     \u001b[1;32melse\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m    117\u001b[0m                         \u001b[1;32mreturn\u001b[0m \u001b[0mf\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mself\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m--> 118\u001b[1;33m             \u001b[1;32mreturn\u001b[0m \u001b[0mfunc\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mself\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mother\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m    119\u001b[0m         \u001b[1;32mreturn\u001b[0m \u001b[0mbinary_op_wrapper\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m    120\u001b[0m     \u001b[1;32mreturn\u001b[0m \u001b[0mpriority_decorator\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;32mC:\\Users\\Mik\\Anaconda2\\lib\\site-packages\\sympy\\core\\expr.pyc\u001b[0m in \u001b[0;36m__pow__\u001b[1;34m(self, other)\u001b[0m\n\u001b[0;32m    149\u001b[0m     \u001b[1;33m@\u001b[0m\u001b[0mcall_highest_priority\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;34m'__rpow__'\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m    150\u001b[0m     \u001b[1;32mdef\u001b[0m \u001b[0m__pow__\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mself\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mother\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m--> 151\u001b[1;33m         \u001b[1;32mreturn\u001b[0m \u001b[0mPow\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mself\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mother\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m    152\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m    153\u001b[0m     \u001b[1;33m@\u001b[0m\u001b[0m_sympifyit\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;34m'other'\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mNotImplemented\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;32mC:\\Users\\Mik\\Anaconda2\\lib\\site-packages\\sympy\\core\\power.pyc\u001b[0m in \u001b[0;36m__new__\u001b[1;34m(cls, b, e, evaluate)\u001b[0m\n\u001b[0;32m    177\u001b[0m             \u001b[1;31m# Only perform autosimplification if exponent or base is a Symbol or number\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m    178\u001b[0m             \u001b[1;32melif\u001b[0m \u001b[1;33m(\u001b[0m\u001b[0mb\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mis_Symbol\u001b[0m \u001b[1;32mor\u001b[0m \u001b[0mb\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mis_number\u001b[0m\u001b[1;33m)\u001b[0m \u001b[1;32mand\u001b[0m \u001b[1;33m(\u001b[0m\u001b[0me\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mis_Symbol\u001b[0m \u001b[1;32mor\u001b[0m \u001b[0me\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mis_number\u001b[0m\u001b[1;33m)\u001b[0m \u001b[1;32mand\u001b[0m\u001b[0;31m\\\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m--> 179\u001b[1;33m                 \u001b[0me\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mis_integer\u001b[0m \u001b[1;32mand\u001b[0m \u001b[0m_coeff_isneg\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mb\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m    180\u001b[0m                 \u001b[1;32mif\u001b[0m \u001b[0me\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mis_even\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m    181\u001b[0m                     \u001b[0mb\u001b[0m \u001b[1;33m=\u001b[0m \u001b[1;33m-\u001b[0m\u001b[0mb\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;32mC:\\Users\\Mik\\Anaconda2\\lib\\site-packages\\sympy\\core\\function.pyc\u001b[0m in \u001b[0;36m_coeff_isneg\u001b[1;34m(a)\u001b[0m\n\u001b[0;32m     81\u001b[0m     \u001b[1;32mif\u001b[0m \u001b[0ma\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mis_Mul\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     82\u001b[0m         \u001b[0ma\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0ma\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0margs\u001b[0m\u001b[1;33m[\u001b[0m\u001b[1;36m0\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m---> 83\u001b[1;33m     \u001b[1;32mreturn\u001b[0m \u001b[0ma\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mis_Number\u001b[0m \u001b[1;32mand\u001b[0m \u001b[0ma\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mis_negative\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m     84\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m     85\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;32mC:\\Users\\Mik\\Anaconda2\\lib\\site-packages\\sympy\\core\\assumptions.pyc\u001b[0m in \u001b[0;36mgetit\u001b[1;34m(self)\u001b[0m\n\u001b[0;32m    242\u001b[0m         \u001b[1;32mexcept\u001b[0m \u001b[0mKeyError\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m    243\u001b[0m             \u001b[1;32mif\u001b[0m \u001b[0mself\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0m_assumptions\u001b[0m \u001b[1;32mis\u001b[0m \u001b[0mself\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mdefault_assumptions\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m--> 244\u001b[1;33m                 \u001b[0mself\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0m_assumptions\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0mself\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mdefault_assumptions\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mcopy\u001b[0m\u001b[1;33m(\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m    245\u001b[0m             \u001b[1;32mreturn\u001b[0m \u001b[0m_ask\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mfact\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mself\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m    246\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;32mC:\\Users\\Mik\\Anaconda2\\lib\\site-packages\\sympy\\core\\assumptions.pyc\u001b[0m in \u001b[0;36mcopy\u001b[1;34m(self)\u001b[0m\n\u001b[0;32m    222\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m    223\u001b[0m     \u001b[1;32mdef\u001b[0m \u001b[0mcopy\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mself\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m--> 224\u001b[1;33m         \u001b[1;32mreturn\u001b[0m \u001b[0mself\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0m__class__\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mself\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m    225\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m    226\u001b[0m     \u001b[1;33m@\u001b[0m\u001b[0mproperty\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;32mC:\\Users\\Mik\\Anaconda2\\lib\\site-packages\\sympy\\core\\assumptions.pyc\u001b[0m in \u001b[0;36m__init__\u001b[1;34m(self, facts)\u001b[0m\n\u001b[0;32m    219\u001b[0m             \u001b[0mself\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0m_generator\u001b[0m \u001b[1;33m=\u001b[0m \u001b[0mfacts\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mgenerator\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m    220\u001b[0m         \u001b[1;32mif\u001b[0m \u001b[0mfacts\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m--> 221\u001b[1;33m             \u001b[0mself\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0mdeduce_all_facts\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mfacts\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m    222\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m    223\u001b[0m     \u001b[1;32mdef\u001b[0m \u001b[0mcopy\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mself\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;32mC:\\Users\\Mik\\Anaconda2\\lib\\site-packages\\sympy\\core\\facts.pyc\u001b[0m in \u001b[0;36mdeduce_all_facts\u001b[1;34m(self, facts)\u001b[0m\n\u001b[0;32m    526\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m    527\u001b[0m                 \u001b[1;31m# lookup routing tables\u001b[0m\u001b[1;33m\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[1;32m--> 528\u001b[1;33m                 \u001b[1;32mfor\u001b[0m \u001b[0mkey\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mvalue\u001b[0m \u001b[1;32min\u001b[0m \u001b[0mfull_implications\u001b[0m\u001b[1;33m[\u001b[0m\u001b[0mk\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mv\u001b[0m\u001b[1;33m]\u001b[0m\u001b[1;33m:\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0m\u001b[0;32m    529\u001b[0m                     \u001b[0mself\u001b[0m\u001b[1;33m.\u001b[0m\u001b[0m_tell\u001b[0m\u001b[1;33m(\u001b[0m\u001b[0mkey\u001b[0m\u001b[1;33m,\u001b[0m \u001b[0mvalue\u001b[0m\u001b[1;33m)\u001b[0m\u001b[1;33m\u001b[0m\u001b[0m\n\u001b[0;32m    530\u001b[0m \u001b[1;33m\u001b[0m\u001b[0m\n",
      "\u001b[1;31mKeyboardInterrupt\u001b[0m: "
     ]
    }
   ],
   "source": [
    "#Probamos a factorizar otro número\n",
    "f=facfc(170168149)\n",
    "print f\n",
    "#Vemos que la factorización que ha salido es buena\n",
    "print 170168149==f[0]*f[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[True, (2048, 2048)]\n",
      "1\n",
      "4\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "(256, 79)"
      ]
     },
     "execution_count": 59,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "facfc(20224)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "{2: 8, 79: 1}"
      ]
     },
     "execution_count": 57,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "factorint(20224)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 102,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "20224"
      ]
     },
     "execution_count": 102,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "256*79"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "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
}