Estudiar los métodos, algoritmos y técnicas de mejora de desempeño necesarias para obtener implementaciones eficientes de operaciones aritméticas en sistemas computacionales con recursos restringidos. Los conceptos y técnicas a ser revisados en este curso harán un énfasis especial en algoritmos de la aritmética de campos finitos y su correspondiente implementación en software [lenguaje C].

Implementaciones de alto desempeño en las tres áreas principales de teoría de códigos: criptografía, códigos de corrección de errores y códigos para compresión/descompresión de datos; dependen significativamente del cómputo eficiente de operaciones aritméticas tales como: suma, resta, multiplicación, inversión, exponenciación modular, raíces cuadradas, etc. Por otro lado, el excelente compromiso costo/desempeño que puede obtenerse en implementaciones en dispositivos de hardware reconfigurable, así como el uso masivo de procesaodres empotrados dentro del paradigma de cómputo ubicuo, han propiciado que diseñadores de muy diversas áreas de Computación y electrónica escojan, cada vez más, estas plataforma para el desarrollo y realización de sus prototipos. Este curso conjunta el estudio teórico de algoritmos de aritmética computacional con el desarrollo de técnicas para obtener implementaciones eficientes de dichos algoritmos en software y hardware.

• Teoría Elemental de Números: Definiciones y Teoremas, números primos y compuestos, teorema fundamental de la aritmética, máximo común divisor, etc.
  Definiciones de campos finitos Campos finitos primos (GF(P)). Campos finitos binarios (GF(2m)).
• Algoritmos Eficientes para aritmética GF(P). Suma y substracción modular.
  Multiplicación Modular y operación de elevar al cuadrado. Inversión modular.
  Pruebas de Primalidad.
• Algoritmos Eficientes para aritmética GF(2m). Suma modular.
  Multiplicación Modular y operación de elevar al cuadrado. Inversión modular.
  Pruebas de Primalidad.
• Exponenciación Modular. Métodos Binarios LSB-First y MSB-Fist. Métodos M-arios.
  Técnicas alternativas.
• Aplicaciones: Introducción al algoritmo de RSA.

• Handbook of Applied Cryptography, Menezes, Oorschot, Vanstone. CRC Press, New York, fifth edition (2001). Portal Internet del libro.

• The Art of Computing Programming, Donald E Knuth, Addison-Wesley, Boston, third edition (2001). Portal Internet del Libro.

• Victor Shoup, "A Computational Introduction to Number Theory and Algebra",  Cambridge University Press, Second Edition, June 2008,
  
• 580 pages..

• Horario de clases: martes y viernes de 16:00 a 18:00 y de 10:00 a 12:00, respectivamente.
  
• 6 de septiembre: Los criterios de evaluación han sido publicados.
• 6 de septiembre: Reglas de etiqueta para entrega de trabajos
• 19 de septiembre: La tarea #1 ha sido publicada
• 15 de octubre: La tarea #2 ha sido publicada.
  Pase para gol para la tarea #2: Ilustración de cómo definir funciones auxiliares y estructuras de datos para esta tarea.
• 6 de diciembre: La tarea #3 ha sido publicada

Examenes



---


Proyectos

• Temas potenciales para el proyecto final
• Proposición del tema a desarrollar: Medianoche del jueves 22 de octubre de 2015
• Entrega de primer avance de proyecto: Medianoche del domingo 22 de noviembre de 2015
• Fecha de entrega final del proyecto: Medianoche del domingo 13 de diciembre de 2015
• Presentaciones de los proyectos: martes 15 de diciembre de 2015

---


Notas de la clase

1. Introducción a la Teoría Elemental de Números.

2. Algoritmos de Aritmética Computacional.

3.  Inverso modular Montgomery y archivos fuentes en C.

4. Exponenciación

5.  Aritmética en campos finitos binarios. Ejemplode la Biblioteca GF de Maple.
   

---


Material de Lectura
• Implementación Eficiente de Aritmética GF(P) en Software: Julio
• Implementación Eficiente de Aritmética GF(2m) en Software: Hankerson
• Reducción con Primos Especiales: Solinas.
• Generación de Secuencias Gold
• Multiplicadores Karatsuba para GF(2m) en hardware
• Multiplicadores Karatsuba para GF(2m) en hardware reconfigurable
• Exponenciador en GF(2m) versión en inglés y versión en castellano.
• Multiplicador Secuencial sobre GF(2m).
• Reducción Modular con pentanomios especiales.
• Multiplicación Montgomery., Artículo de Tolga
• Inversión con algoritmo de Montgomery.
• Códigos Reed-Solomon: Biblioteca para Maple
• Inversión Using Addition Chains
• An Artificial Immune System Heuristic for Generating Short Addition Chains
• Parallel Itoh-Tsujii Multiplicative Inversion Algorithm for a Special Class of Trinomials
  

---


Calendario




Semana	Día	Material	Observaciones
1	2 de septiembre	Introducción
2	7 y 9 de septiembre	Introducción y teoría Elm. de Números	Publicación de tarea #1
3	14  y 16 de septiembre	Introducción y teoría Elm. de Números
4	21 y 23 de septiembre	Teoría elemental de números, Aritmética modular
5	28 y 30 de septiembre	Prácticas de laboratorio	Prácticas de laboratorio con Magma [a cargo del Dr. Luis Domínguez]
6	5 y 7 de octubre	Aritmética modular	propuestas de proyectos, entrega de tarea #1
7	12 y 14 de octubre	Exponenciación	Publicación de tarea #2
8	19 y 21 octubre	Sin clases	The São Paulo Advanced School of Cryptography
9	28 de octubre	Aritmética en campos finitos binarios
10	4 de noviembre	Aritmética en campos finitos ternarios	entrega de tarea #2
11	9 y 11 de noviembre	Torres de campo primas
12	16 y 18 de noviembre	Torres de campo binarias/ternarias	Primer avance de proyecto Publicación de tarea #3
13	23 y 25 de noviembre	Torres de campo binarias/ternarias	Segundo avance de proyecto
14	30 de noviembre, 2 de diciembre	Aritmética de curvas elípticas	entrega de tarea #3
15	7 y 9 de diciembre	Aritmética de curvas elípticas
16	13 y 15 de diciembre	Examen final, entrega y presentación de proyectos