[Todos CMAT] SAGA: charla de Gonzalo Tornaría, HOY viernes
Gonzalo Tornaria
tornaria en cmat.edu.uy
Vie Nov 24 07:57:52 UYT 2006
Horario: Viernes 24/Nov, de 14 a 16
Lugar: Salón de seminarios, piso 16
Expositor: Gonzalo Tornaría
Título:
Raíces cuadradas módulo p
Resumen:
Consideramos el problema de calcular raíces cuadradas módulo un
primo p. Este problema tiene aplicaciones, por ejemplo, a sistemas
de criptografía basados en curvas elípticas.
El algoritmo de Tonelli y Shanks, basado en logaritmos discretos,
es el más usado, y posiblemente el más rápido cuando se promedia
sobre todos los números primos. Sin embargo, para algunos primos
particulares el algoritmo de Tonelli y Shanks no es bueno, y otros
algoritmos son considerablemente más rápidos.
Presentaremos una comparación del algoritmo de Tonelli y Shanks
con un algoritmo de Cipolla basado en extensiones cuadráticas de
cuerpos finitos, y daremos condiciones explícitas sobre un número
primo que decidan cuál algoritmo es más rápido.
Finalmente comentaremos un ejemplo de su aplicación al sistema
Diffie-Hellman en la curva elíptica NIST P-224.
Más información sobre la lista de distribución Todos