Practica 5 - Test de primalidad .ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Test de Primalidad"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La función <span style=\"color:blue\">random</span>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import random"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "from sympy import *"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.6994257981432691"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "random.random()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "random.randint(1, 4)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Test 1: Pseudoprimos"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- **Ejercicio 1.** Define una función <span style=\"color:red\">psp(n)</span> con salida <span style=\"color:green\">(b,true)</span> o <span style=\"color:green\">(b,false)</span> y que haga los siguiente:\n",
    "    1. Elige una base $b$ al azar.\n",
    "    2. Comprueba si $gcd(b,n)=1$. \n",
    "        - Si es falso la función termina con la salida: \n",
    "            - <span style=\"color:green\"> print $gcd(b,n)$ es divisor de $n$</span>.\n",
    "            - (b,false)\n",
    "        - Si es cierto comprueba si $b^{(n-1)}\\equiv 1 \\mbox{ mod } n$, \n",
    "            - Si es falso la salida es <span style=\"color:green\">(b,false)</span>.\n",
    "            - Si es cierto la salida es <span style=\"color:green\">(b,true)</span>. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def psp(n1):\n",
    "    #Cambiamos el número entero por su asociado positivo\n",
    "    n=abs(n1)\n",
    "    #Nos quitamos los casos triviales, n=0,1,2\n",
    "    if n<=1:\n",
    "        print \"0 y 1 no son primos\"\n",
    "        return(false)\n",
    "    if n==2:\n",
    "        return (true)\n",
    "    #Elegimos un número positivo entre 2 y n-1\n",
    "    b=random.randint(2,n-1)\n",
    "    #Comprobamos si el mcd entre el numero aleatorio b y n es 1\n",
    "    #Si no 1 obtenemos que el mcd divide a n\n",
    "    if gcd(b,n)!=1:\n",
    "        print 'El gcd de',b,'y', n,'es divisor de',n\n",
    "        return (b,false)\n",
    "    #Si b y n son primos relativos comprobamos si n es pseudoprimo respecto de la base b\n",
    "    else:\n",
    "        if(pow(b,n-1,n)==1):\n",
    "            return (b,true)\n",
    "        else:\n",
    "            return (b,false)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- **Ejecicio 2.** Define una función <span style=\"color:red\">pspk(n,k)</span> que realice hasta k veces la función <span style=\"color:red\">psp(n)</span>. \n",
    "    - Si en algún momento n falla el test la función termina con <span style=\"color:green\">(b,false</span>,\n",
    "    con b la base para la cual n falla el test. \n",
    "    - Si pasa el test para las k bases elegidas la salida será:\n",
    "        - <span style=\"color:green\"> print \"es posible que n sea primo\"</span>\n",
    "        - <span style=\"color:green\"> retun (b,true)</span>\n",
    "   puedes poner la última base o las k bases que has ido eligiendo.\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "def pspk(n,k):\n",
    "    #Lista donde guardaremos las bases usadas en el test\n",
    "    b1=[]\n",
    "    #Hacemos la prueba de pseudoprimo k veces\n",
    "    for i in range(0,k):\n",
    "        b=psp(n)\n",
    "        #Vamos imprimiendo la base que escogemos, si obtenemos que es pseudoprimo imprimos 'true'\n",
    "        if b[1]==true:\n",
    "            b1=b1+[b[0]]\n",
    "            print b\n",
    "            \n",
    "        #Si encontramos que no es primo, devolvemos 'false' y la base para la cual lo es\n",
    "        else:\n",
    "            b1=b1+[b[0]]\n",
    "            return (b1,false)\n",
    "    #Si el primo pasa k veces el test imprimimos que es posible que sea primo y devolvemos la última base\n",
    "    print 'Es posible que el número sea primo'\n",
    "    return (b1,true)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Test 2: Pseudo primos de Euler. Test de Slovay-Strassen"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "EL símbolo de Jacobi"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    " from sympy.ntheory import jacobi_symbol"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "-1"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "jacobi_symbol(7,45)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Recordamos que $n$ es pseudo primo de Euler respecto a la base $b$ si:\n",
    "\n",
    "- $n$ es impar, \n",
    "$$\\qquad$$\n",
    "\n",
    "- $gcd(b,n)=1$ y \n",
    "$$\\qquad$$\n",
    "\n",
    "- $b^{\\frac{n-1}{2}}\\equiv jacobi(b,n) \\mbox{ mod } n$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- **Ejercicio 3.** Define la función <span style=\"color:red\">epsp(n)</span> que:\n",
    "    1. Si $n$ es par tiene como salida:\n",
    "        - <span style=\"color:green\">print n es par</span>\n",
    "        - <span style=\"color:green\">return (2,false)</span>\n",
    "    2. Elije una base $b$ al azar.\n",
    "    3. Comprueba si $gcd(b,n)=1$ \n",
    "       - Si es falso la función termina con:\n",
    "         - <span style=\"color:green\">print gcd(b,n) es divisor de n</span> \n",
    "         - <span style=\"color:green\"> return (b,false)</span> \n",
    "       - Si es cierto comprueba si $b^{\\frac{n-1}{2}} \\equiv jacobi(b,n) \\mbox{ mod } n$, \n",
    "          - si es falso la salida es <span style=\"color:green\">(b,false)</span>,\n",
    "          - si es cierto la salida es <span style=\"color:green\">(b,true)</span>. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def epsp(n1):\n",
    "    #Cambiamos el número entero por su asociado positivo\n",
    "    n=abs(n1)\n",
    "    #Quitamos casos triviales n=0,1,2\n",
    "    if n<=1:\n",
    "        print \"0 y 1 no son primos\"\n",
    "        return false\n",
    "    if n==2:\n",
    "        return true\n",
    "    #Comprobamos si el número es par\n",
    "    #Si es par devolvemos que no es primo \n",
    "    if n%2==0:\n",
    "        print n,'es par'\n",
    "        return (2,false)\n",
    "    #Elegimos una base b al azar \n",
    "    b=random.randint(2,n-1)\n",
    "    #Comprobamos si el mcd entre el numero aleatorio b y n es 1\n",
    "    #Si no 1 obtenemos que el mcd divide a n\n",
    "    if gcd(b,n)!=1:\n",
    "        print 'El gcd de',b,'y', n,'es divisor de',n\n",
    "        return (b,false)\n",
    "    else:\n",
    "        #Comprobamos la condición de euler y devolvemos 'true' o 'false' y la base dependiendo si pasa el test o no\n",
    "        if(pow(b,(n-1)/2,n)==(jacobi_symbol(b,n))%n):\n",
    "            return (b,true)\n",
    "        else:\n",
    "            return (b,false)\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- **Ejercicio 4.** Define una función <span style=\"color:red\">epsp(n,k)</span> que realice hasta k veces el test 2. \n",
    "    - Si en algún momento $n$ falla el test la función termina con <span style=\"color:green\">(b,false)</span>,\n",
    "      con $b$ la base para la cual $n$ no pasa el test. \n",
    "    - Si $n$ pasa el test para las $k$ bases elegidas la salida será:\n",
    "        - <span style=\"color:green\"> print es posible que n sea primo</span>\n",
    "        - <span style=\"color:green\"> return (b,true)</span>, puedes poner las última base o las k bases."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def epspk(n,k):\n",
    "    #Lista donde guardaremos las bases usadas en el test\n",
    "    b1=[]\n",
    "    #Hacemos la prueba de pseudoprimo k veces\n",
    "    for i in range(0,k):\n",
    "        b=epsp(n)\n",
    "        #Vamos imprimiendo la base que escogemos, si obtenemos que es pseudoprimo imprimos 'true'\n",
    "        if b[1]==true:\n",
    "            b1=b1+[b[0]]\n",
    "            print b\n",
    "            \n",
    "        #Si encontramos que no es primo, devolvemos 'false' y la base para la cual lo es\n",
    "        else:\n",
    "            b1=b1+[b[0]]\n",
    "            return (b1,false)\n",
    "    #Si el primo pasa k veces el test imprimimos que es posible que sea primo y devolvemos la última base\n",
    "    print 'Es posible que el número sea primo'\n",
    "    return (b1,true)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Test 3. Fuertemente pseudoprimos. Test de Miller-Rabin"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Recordar que $n$ es ***fuertemente pseudoprimo*** respecto a la base $b$ si: \n",
    "   - $n$ es impar, \n",
    "   - $gcd(b,n)=1$ y \n",
    "   - Si escribimos $n=2^s t$, con $t$ impar, entonces:\n",
    "       - $b^t \\equiv 1 \\mbox{ mod } n$ o bien,\n",
    "       - existe $i=0,1,\\ldots,s-1$ tal que $b^{t * 2^i}\\equiv -1 \\mbox{ mod } n$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- **Ejercicio 5.** Define una función <span style=\"color:red\">mpot(p,m)</span> que calcule la mayor potencia de $p$ que divide a $m$. \n",
    "\n",
    "No usar funciones que factoricen m."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "def mpot(p,m):\n",
    "    #Quitamos casos triviales\n",
    "    if p==0 or p==1:\n",
    "        return \"Es una trivialidad preguntarse cual es la mayor potencia de 0 o 1 que divide a m\"\n",
    "    #Comprobamos si p divide a m\n",
    "    if m%p!=0:\n",
    "        print p,' no divide a ',m\n",
    "        return (1,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 la máxima potencia de a que divide a m, con su exponente\n",
    "        return a,i\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- **Ejercicio 6.**  Define una función <span style=\"color:red\">fpsp(n)</span> que:\n",
    "    - **1.** Si $n$ es par tiene como salida <span style=\"color:green\"> print n es par, return (2,false)</span>.\n",
    "    - **2.** En otro caso:\n",
    "        - **2.1.** Calcule $s$ y $t$ tales que $n-1 = 2^s t$, con $t$ impar.\n",
    "        - **2.2.** Elije una base $b$ al azar.\n",
    "        - **2.3.** Comprueba si $gcd(b,n)=1$ \n",
    "             - ***2.3.1.*** Si es falso la función termina con <span style=\"color:green\"> print gcd(b,n) es divisor de n, return (b false)</span>. \n",
    "             - ***2.3.2.*** Si es cierto comprueba si $b^t= \\pm  1\\mbox{ mod } n$: \n",
    "                  - ***2.3.2.1.*** Si es cierto la salida es <span style=\"color:green\">(b,true)</span>, \n",
    "                  - ***2.3.2.2.*** Si es falso comprueba:\n",
    "                      - **2.3.2.2.1.** Si existe un $i=1,\\ldots,s-1$ tal que $b^{t*2^i}\\equiv  -1 \\mbox{ mod } n$ la salida es <span style=\"color:green\">(i,b,true)</span> (sacar i es opcional).\n",
    "                      - **2.3.2.2.2.** Si no existe tal $i$ la salida es <span style=\"color:green\">(b, false)</span> . \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "def fpsp(n1):\n",
    "    #Convertimos el entero n1 en su asociado positivo n\n",
    "    n=abs(n1)\n",
    "    \n",
    "    #Quitamos casos triviales n=0,1,2\n",
    "    if n<=1:\n",
    "        print \"0 y 1 no son primos\"\n",
    "        return false\n",
    "    if n==2:\n",
    "        return true\n",
    "    \n",
    "    #Comprobamos si es par, si es par no es primo\n",
    "        print n,'es par'\n",
    "        return (2,false)\n",
    "    else:\n",
    "        r=mpot(2,n-1)\n",
    "        s=r[1]\n",
    "        t=(n-1)/r[0]\n",
    "        b=random.randint(2,n-1)\n",
    "        if gcd(b,n)!=1:\n",
    "            print 'El gcd de',b,'y', n,'es divisor de',n\n",
    "            return (b,false)\n",
    "        else:\n",
    "            if pow(b,t,n)==1 or pow(b,t,n)==n-1:\n",
    "                return (b,true)\n",
    "            else:\n",
    "                for i in range(1,s):\n",
    "                    if pow(b,t*(2**i),n)==n-1:\n",
    "                        return(b,true)\n",
    "            \n",
    "            return (b,false)\n",
    "    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- **Ejercicio 7.**  Define una función <span style=\"color:red\">fpsp(n,k)</span>  que aplique hasta $k$ veces el test 3. \n",
    "    - Si en algún momento $n$ no pasa el test la función termina con <span style=\"color:green\">(b,false)</span>.\n",
    "    - Si $n$ pasa el test para las $k$ bases elegidas la salida será <span style=\"color:green\">print es posible que n sea primo, (bases, true)</span>"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "def fpspk(n,k):\n",
    "    #Lista donde guardaremos las bases usadas en el test\n",
    "    b1=[]\n",
    "    #Hacemos la prueba de pseudoprimo k veces\n",
    "    for i in range(0,k):\n",
    "        b=fpsp(n)\n",
    "        #Vamos imprimiendo la base que escogemos, si obtenemos que es pseudoprimo imprimos 'true'\n",
    "        if b[1]==true:\n",
    "            b1=b1+[b[0]]\n",
    "            print b\n",
    "            \n",
    "        #Si encontramos que no es primo, devolvemos 'false' y la base para la cual lo es\n",
    "        else:\n",
    "            b1=b1+[b[0]]\n",
    "            return (b1,false)\n",
    "    #Si el primo pasa k veces el test imprimimos que es posible que sea primo y devolvemos la última base\n",
    "    print 'Es posible que el número sea primo'\n",
    "    return (b1,true)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Comparaciones"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- **Ejercicio 8.** Comprueba los tres tests, usando números grandes y algún número de Carmichael, y compáralos con el test de Sympy <span style=\"color:blue\">isprime</span>  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Primer ejemplo: número primo grande\n",
    "Vamos a elegir el siguiente primo a $10^{100}$ y comprobaremos que tal van los tests."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "10000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000267\n"
     ]
    }
   ],
   "source": [
    "n=nextprime(10**100)\n",
    "print n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Comprobamos con sympy que es primo lógicamente."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "isprime(n)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Usamos los test que hemos programado para comprobar que efectivamente este número primo pasa los tres test ejecutados de manera sucesiva, dejando la probabilidad de que el número sea primo muy alta."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(5958854664402331763846242577703958179444941724529368154822089590586761806119333866082973611542692022L, True)\n",
      "(8776075989578475171080765019343477906560529410914114580615376750156905060890873904598967732347035498L, True)\n",
      "(6418492224170280863845897805399212310419611284409574480502569399489641728218399287447667765733506753L, True)\n",
      "(9602399157634399923606899487387397058353677627689753738518120798195119568573738272919975000987226921L, True)\n",
      "(7616919516603530072955649162065554035622616665651832776572998883246880031506582897099459646861586622L, True)\n",
      "(6225754880299588163538274514725597904034708682499317490060009599351280697001532273094538812031500355L, True)\n",
      "(9587770608799361530551383414862290163876582346022177274783114726848137537598024702360956419987963289L, True)\n",
      "(8239986100699466674376873560798550902445425232590829819165160054616090350303633069344758971604624424L, True)\n",
      "(9545921100148658751217311001117576930602499418683961694096624774561354008580813993888896790669813898L, True)\n",
      "(460178231760301468568823582373679198920525949645176262506819387402020013175459369268945482576763509L, True)\n",
      "Es posible que el número sea primo\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "([5958854664402331763846242577703958179444941724529368154822089590586761806119333866082973611542692022L,\n",
       "  8776075989578475171080765019343477906560529410914114580615376750156905060890873904598967732347035498L,\n",
       "  6418492224170280863845897805399212310419611284409574480502569399489641728218399287447667765733506753L,\n",
       "  9602399157634399923606899487387397058353677627689753738518120798195119568573738272919975000987226921L,\n",
       "  7616919516603530072955649162065554035622616665651832776572998883246880031506582897099459646861586622L,\n",
       "  6225754880299588163538274514725597904034708682499317490060009599351280697001532273094538812031500355L,\n",
       "  9587770608799361530551383414862290163876582346022177274783114726848137537598024702360956419987963289L,\n",
       "  8239986100699466674376873560798550902445425232590829819165160054616090350303633069344758971604624424L,\n",
       "  9545921100148658751217311001117576930602499418683961694096624774561354008580813993888896790669813898L,\n",
       "  460178231760301468568823582373679198920525949645176262506819387402020013175459369268945482576763509L],\n",
       " True)"
      ]
     },
     "execution_count": 16,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pspk(n,10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(9724721390111824788921019770367363901915961931925453988833834952713557326791129199530290068294648706L, True)\n",
      "(992135127129660437102322276462288667552808327770173872126145432985266391234428238062662787095461302L, True)\n",
      "(4811320683964771522884730486650759338154196737013821364721121699687649955745394700125379120393764121L, True)\n",
      "(3172881046772453120051133403246359893346503069650468343494850184231339485051852707677102933503133753L, True)\n",
      "(8576306951272395700914990316717284184324854455219279713930127181393386413673056421189609042375141599L, True)\n",
      "(2870259426520664463403201498140598560294871968305286747707564585065346492686525563180788437694970222L, True)\n",
      "(2409397795487071832694702669223469591173022860811273589705466159738220144177856169700463395955785787L, True)\n",
      "(6870867692427146274247870861948068822197123607823196928564157798436881142238364120352452376545012314L, True)\n",
      "(2498401235024074726316926921822080669283158254422450573280608135848578406448675727026440176784316034L, True)\n",
      "(4539846775139052868287881667932935427003955406449648580210609456651006792670387232548738212351740829L, True)\n",
      "Es posible que el número sea primo\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "([9724721390111824788921019770367363901915961931925453988833834952713557326791129199530290068294648706L,\n",
       "  992135127129660437102322276462288667552808327770173872126145432985266391234428238062662787095461302L,\n",
       "  4811320683964771522884730486650759338154196737013821364721121699687649955745394700125379120393764121L,\n",
       "  3172881046772453120051133403246359893346503069650468343494850184231339485051852707677102933503133753L,\n",
       "  8576306951272395700914990316717284184324854455219279713930127181393386413673056421189609042375141599L,\n",
       "  2870259426520664463403201498140598560294871968305286747707564585065346492686525563180788437694970222L,\n",
       "  2409397795487071832694702669223469591173022860811273589705466159738220144177856169700463395955785787L,\n",
       "  6870867692427146274247870861948068822197123607823196928564157798436881142238364120352452376545012314L,\n",
       "  2498401235024074726316926921822080669283158254422450573280608135848578406448675727026440176784316034L,\n",
       "  4539846775139052868287881667932935427003955406449648580210609456651006792670387232548738212351740829L],\n",
       " True)"
      ]
     },
     "execution_count": 17,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "epspk(n,10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(8572220347667578388048486736401027081258740083048015487490590974405893398716222932662211834587568778L, True)\n",
      "(926974789254538525140710619525009452586837462376090735867798211662752755879606967713823116924930573L, True)\n",
      "(2246419763853538507750950851448725545473550376522691147189312400436837586413047120166529652652494317L, True)\n",
      "(1639246011027821890558993777400921135362391393738100162238071641317870291648889669879112751815130877L, True)\n",
      "(4280562066756062869955078233429849708586146928948050387897441481842943699105047320698008194854700058L, True)\n",
      "(5144761994981984633548874596452943547923890814912753506708720248137680111609106209006383961307933L, True)\n",
      "(7913660030624369892953631490523502131626100681713205407724406592608712002546138818757057568791089766L, True)\n",
      "(7922558169979501750453925895743120816952251250932192682894814283997331300733173651220567670076419532L, True)\n",
      "(6293386058066124063195560515791473584075350850685738589300017132022639895244231404386836393346702764L, True)\n",
      "(1008950338769386165240853609652090555137007356647179752146663490124175225627548071284971612123095866L, True)\n",
      "Es posible que el número sea primo\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "([8572220347667578388048486736401027081258740083048015487490590974405893398716222932662211834587568778L,\n",
       "  926974789254538525140710619525009452586837462376090735867798211662752755879606967713823116924930573L,\n",
       "  2246419763853538507750950851448725545473550376522691147189312400436837586413047120166529652652494317L,\n",
       "  1639246011027821890558993777400921135362391393738100162238071641317870291648889669879112751815130877L,\n",
       "  4280562066756062869955078233429849708586146928948050387897441481842943699105047320698008194854700058L,\n",
       "  5144761994981984633548874596452943547923890814912753506708720248137680111609106209006383961307933L,\n",
       "  7913660030624369892953631490523502131626100681713205407724406592608712002546138818757057568791089766L,\n",
       "  7922558169979501750453925895743120816952251250932192682894814283997331300733173651220567670076419532L,\n",
       "  6293386058066124063195560515791473584075350850685738589300017132022639895244231404386836393346702764L,\n",
       "  1008950338769386165240853609652090555137007356647179752146663490124175225627548071284971612123095866L],\n",
       " True)"
      ]
     },
     "execution_count": 18,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "fpspk(n,10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Segundo ejemplo: número como producto de dos números primos grandes."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Cogeremos ahora un número $n1$ como el producto de dos números primos grandes del orden de $10^{70}$ y $10^{30}$, efectivamente la función isprime($n1$) nos devuelve que el número no es primo."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "False\n",
      "10000000000000000000000000000570000000000000000000000000000000000000033000000000000000000000000001881\n"
     ]
    }
   ],
   "source": [
    "n1=nextprime(10**70)*nextprime(10**30)\n",
    "print isprime(n1)\n",
    "print n1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Vemos efectivamente que los test nos devuelven que el número no es primo."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "([7040883654408828129813358333931648603831704913754396128656515321189260713215645487651495558310115277L],\n",
       " False)"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pspk(n1,10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "([6492535506004019792262762015273397811483612110783528225913208731324862408028037024381169174928308259L],\n",
       " False)"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "epspk(n1,10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "([860825004109311242226919770039680348124053243825081503061350300727884064020417635239457622179872603L],\n",
       " False)"
      ]
     },
     "execution_count": 22,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "fpspk(n1,10)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Tercer ejemplo: Primo de CarMichael 561"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "isprime(561)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(304, True)\n",
      "(452, True)\n",
      "(421, True)\n",
      "Es posible que el número sea primo\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "([304, 452, 421], True)"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pspk(561,3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "([58], False)"
      ]
     },
     "execution_count": 25,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "epspk(561,3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(305, True)\n",
      "El gcd de 341 y 561 es divisor de 561\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "([305, 341], False)"
      ]
     },
     "execution_count": 26,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "fpspk(561,3)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Después de varias pruebas obtenemos que el test 1 siempre lo pasa a no ser que la base escogida no sea primo relativo con 561 incluso llegándolo a pasar 3 veces, el test 2 lo pasa 1 vez como mucho, y el test 3 no lo ha pasado en ninguna de las pruebas hechas."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Cuarto ejemplo: Primo de CarMichael 46657"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "False"
      ]
     },
     "execution_count": 27,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "isprime(46657)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Vemos que no es primo."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(17360, True)\n",
      "(39133, True)\n",
      "(31646, True)\n",
      "(44742, True)\n",
      "(3636, True)\n",
      "Es posible que el número sea primo\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "([17360, 39133, 31646, 44742, 3636], True)"
      ]
     },
     "execution_count": 28,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "pspk(46657,5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "El gcd de 11375 y 46657 es divisor de 46657\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "([11375], False)"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "epspk(46657,5)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "El gcd de 299 y 46657 es divisor de 46657\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "([299], False)"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "fpspk(46657,5)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Obtenemos un resultado análogo al anterior primo de CarMichael"
   ]
  },
  {
   "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
}