GIIT_AMA_1718_T1_Ejercicios_Grupos

538 days ago by GIIT_AMA_1718

Práctica de Ampliación de Matemáticas (Tema 1. Teoría de números)

Alumnos que integran el grupo

  1. ...
  2. ...
  3. ..,

Ejercicios

En los siguientes ejercicios se tratará de codificar funciones sencillas de teoría de números, para repasar los conceptos y algoritmos. Sage tiene predefinidas montones de funciones que hacen todas esas operaciones, pero el objetivo es que vosotros aprendáis cómo se trabaja con números enteros, por lo que en la resolución deberéis usar únicamente lo que se ha explicado en las prácticas (o las que aparecen al final de la práctica). Las funciones tienen que estar convenientemente explicadas, con un comentario al comienzo de la función como líneas de comentario en cada operación que se considere compleja (en particular en los bucles y llamadas recursivas).

 
       

 

A.Programad el apartado 1 y elegid entre los apartados 2 al 4 aquel que al sumarlo a la suma de los DNIs del grupo se obtenga un múltiplo de 3.

  1. Potenciación modular. Crea una función que reciba tres números, b,m,n y calcule el resto de dividir $b^m$ entre $n$. En lugar de utilizar la función $\phi$ (para la que se necesita una factorización) usad el siguiente método recursivo: si m=1, devolverá b. Si m es par, calculará $B=b^{m/2}$ y devolverá $B^2$. Si m es impar, calculará $B=b^{(m-1)/2}$ y devolverá $b B^2$.
  2. Decimos que un número $n$ es pseudoprimo base b si $b^{n-1}\equiv_m 1$. Elige un número primo $b$ menor que 20 (y mayor o igual a 3) y calcula un pseudoprimo (no primo) base $b$.
  3. Los números de Carmichael son aquellos números $n$ que verifican que $a^{n-1}\equiv_n 1$ para todo $a$ tal que $mcd(a,n)=1$. Encuentra un número de Carmichael que sea múltimo de tres primos, siendo el menor de ellos 7.
  4. Un número $n$ es de Poulet si $2^{n-1}\equiv_n 1$. Encontrar todos los números de Poulet menores que 1000 y determinar cuáles no son primos.
 
       

B. Algoritmo RSA

 Comencemos con una introducción al problema:

El algoritmo RSA funciona del siguiente modo:

Partimos de dos números primos, p y q. Tomamos $n=pq$ como nuestro tamaño de palabra, es decir, tenemos que codificar el mensaje en un número en base $n$.

Supongamos que ya hemos hecho este proceso y que $m$ es una palabra de nuestro mensaje (debería modificarse para ser prima con $n$, pero vamos a obviar este paso).

Además, necesitamos un número $e$ coprimo con $\phi(n)$ y $d$, su inverso módulo $\phi(n)$ ($ed\equiv_{\phi(n)} 1$).

Para codificar nuestro mensaje, basta hacer $m_c=m^e$. Y $m_c$ será el mensaje codificado.

Para decodificarlo, hacemos $m_c^d\equiv_{n} m^{de}\equiv_n m$.

La clave pública estará formada por $n$ y $e$.

La clave privada será $d$.

Ejercicios:

  1. Tomando p=45196021368097381904586622354492733161, q=173905113088091315885542665902416112387 y e=367, crea una función que reciba una cadena de texto y la devuelva como un número encriptado con RSA y otra que reciba el número encriptado y devuelva la cadena original.
  2. Crea la clave pública y privada (usa el procedimiento que aparece en Wikipedia).
 
       

MISCELÁNEA

Las siguientes funciones son para simplificar los ejercicios del algoritmo RSA.

%auto def texto_a_numero(texto): # Recibe un texto y devuelve la lista de valores ASCII de sus caracteres. return [ord(k) for k in texto] def numero_a_texto(numero): # Recibe una lista de valores ASCII y devuelve un texto texto='' for k in numero: texto+=unichr(k) return texto 
       
# Pasamos un mensaje a texto: msg_numero=base10(texto_a_numero(u'¡Hola Mundo!'),255) msg_numero 
       
9912134678503849586690185421
9912134678503849586690185421
# Y recuperamos el mensaje: print numero_a_texto(msg_numero.digits(255)) 
       
¡Hola Mundo!
¡Hola Mundo!
# Para generar números aleatorios muy grandes import random as rnd Z = IntegerRing() p=Z(rnd.getrandbits(128)) p 
       
40469289386228221094370757167034237725
40469289386228221094370757167034237725
# Y para comprobar si el número generado es primo: p.is_prime() 
       
False
False
 
       

Planificación y trabajo en equipo

Trabajo en equipo

Cada miembro del equipo, deberá subir una memoria que contenga, al menos, los siguientes items:

  • Metodología seguida. Indicar cómo se ha organizado el trabajo, en qué tareas se ha dividido y a quien han sido asignadas. 
  • Calendario de trabajo. Indicar las reuniones que se vayan a programar y cómo se realizará la coordinación entre los miembros del equipo.
  • Incidencias. 

Planificación

Cada alumno debe subir una memoria con los siguientes puntos:

  • Planificación inicial. Una vez que se haya producido el reparto de tareas del equipo, deberá elaborar una planificación donde figurarán las distintas tareas que debe realizar, un tiempo estimado para cada una y el periodo de tiempo en el que lo realizará.  
  • Tiempo total empleado y tiempo empleado en cada tarea. 

Normas de entrega

  1. Rellenar en la parte superior el nombre de los integrantes del grupo.
  2. Compartir esta hoja de Sage con el profesor (GIIT16trinidad).
  3. En el desplegable "File" de la parte superior de la página, elegir "Print"
  4. Imprimir la página resultante como pdf. 
  5. Subirla al campus virtual antes de la fecha límite, junto con la memoria de planificación y trabajo en equipo. Cada día a partir de la fecha límite, la nota sobre la que se puntúa el ejercicio bajará en un punto.

Criterios de evaluación

  • 40% de la calificación que los resultados y métodos aplicados sean correctos.
  • 15% de la calificación que los resultados estén correctamente explicados.
  • 15% de la calificación que los métodos empleados sean los más adecuados al problema.
  • 15% de la calificación que el trabajo haya sido convenientemente planificado (http://matematicas.unex.es/~trinidad/misc/planificacion.rubrica.pdf).
  • 15% de la calificación que se haya organizado el trabajo en equipo (http://matematicas.unex.es/~trinidad/misc/trabajo.equipo.rubrica.pdf).