Participación del GID-24 en la Jornadas Galileanas

1) Nombre del grupo o investigador

Algoritmos para Matemáticas Discretas. Grupo GID-24

2) Integrantes del grupo

Pedro Berrizbeitia.

Thomas Berry.

Reinaldo Giudici.

Boris Iskra.

Alberto Mendoza.

Aurora Olivieri.

Domingo Quiroz.

Mercedes Rosas.

3)  Objetivos generales del grupo

El grupo tiene por objetivo el desarrollo de algoritmos en diversos temas de Matemáticas Discretas. El énfasis se ha puesto en temas relacionados con el problema de distinguir los números primos de los números compuestos y en la búsqueda de primos grandes por la relación e impacto que estos temas tienen en el mundo de la seguridad en las comunicaciones.

4)  Antecedentes

La década de los noventa se caracterizó por el acceso, por parte de muchos matemáticos en todo el mundo, a una inmensa capacidad computacional que ha contribuido a revolucionar el desarrollo las Matemáticas, aún de aquellas consideradas más clásicas. En particular, la publicación en 1976 del llamado RSA, un sistema de encriptación de mensajes, basado en resultados de la Teoría de Números desarrollada en los siglos XVII y XVIII, ha resultado en un fuerte desarrollo de la investigación en primalidad y factorización. Otras áreas de las Matemáticas Discretas se han visto afectadas de manera similar, tales como la Combinatoria Algebraica, la Teoría de Grafos, entre otras, áreas que también son objeto actualmente de la investigación de profesores del grupo. La creación de este grupo de investigación surgió como consecuencia de la coincidencia en la percepción que varios profesores del departamento tuvimos sobre este fenómeno computacional y del interés que compartíamos en problemas concretos en varias de estas áreas.

5)  Logros en los últimos 5 años: publicaciones, tesis, proyectos,
convenios, patentes, conferencias invitadas

Lista de publicaciones:

Libros:

Berrizbeitia, P. "Algoritmos Deterministas de Primalidad". Escuela Venezolana de Matemáticas, Asociación Matemática Venezolana, Centro de Estudios Avanzados, Ivic.. Caracas, Venezuela. 2004. ISBN: 980-261-077-1

Artículos:

1)Berrizbeitia, P; Berry, T. Biquadratic reciprocity and a Lucasian primality test Pedro Berrizbeitia; T. G. Berry Math. Comp. 73 (2004), 1559-1564. . (2004). MATHEMATICS OF COMPUTATION. . Indexada en el SCIENCE CITATION INDEX. Vol. 73, pp. 1559 - 1564

2)Berrizbeitia, P; Giudici, R.. On Cycles in the sequence of Unitary Cayley Graphs.. (2004). DISCRETE MATHEMATICS. . Indexada en el SCIENCE CITATION INDEX. Vol. 282, no.1-3, pp. 239 - 243

3)Berrizbeitia, P; Siguna Mueller; Hugh C. Williams. Pseudocubes and Primality Testing. (2004) Algorithmic Number Theory Symposium: ANTS - VI. "Lecture Notes in Computer Science (LNCS)". Vol. 3076. pp. 102 - 116

4)Berrizbeitia, P; Berry, T; Tena -Ayuso, Juan. A Generalization of the Proth Theorem. . (2003). ACTA ARITHMETICA. . Indexada en el SCIENCE CITATION INDEX. Vol. 107, pp. 115 - 110.2

5)Berrizbeitia, P; Odreman, M.; Tena, Juan. Primality test for numbers M with a large power of 5 dividing M^4 - 1.. (2003). THEORETICAL COMPUTER SCIENCE. . Indexada en el SCI. Vol. 297, pp. 25 – 36

6)Olivieri, A.; del Río, Ángel (adelrio@um.es). "An algorithm to compute the primitive central idempotents and the Wedderburn decomposition of a rational group algebra ". JOURNAL OF SYMBOLIC COMPUTATION. 2003. Indexada en el SCIENCE CITATION INDEX. Artículo Invitado. Vol. 35, pp. 673 – 687

7)Rosas, Mercedes Helena. "Los numeros de (Euler)-Catalan". Boletin de la Sociedad Matematica Venezolana. 2003. Indexada en el MathSciNet. Artículo Invitado. Vol. X, pp. 43 - 58

8)Boulton, L.; Rosas, Mercedes Helena. "Sumando la derivada de la serie geometrica". Boletin de la Asociacion Matematica Venezolana. 2003. Indexada en el Math Review. Vol. 10, pp. 89 - 98

9)Berrizbeitia, P; Iskra, B.. Deterministic primality test for numbers of the form $Asp 2.3sp n+a, nge3$ odd,. (2002). PROCEEDINGS OF THE AMERICAN MATHEMATICAL SOCIETY. . Indexada en el SCI. Vol. 130, no2, pp. 363 – 365

10)Rosas, Mercedes Helena. "Specializations of MacMahon symmetric functions and the polynomial algebra". DISCRETE MATHEMATICS. 2002. Indexada en el SCI. Artículo Invitado. Vol. 246, pp. 285 - 293

11)Rosas, Mercedes Helena; Rota, Gian-Carlo; Stein, Joel. "A combinatorial overview of the plethystic Hopf algebra of vector symmetric functions.". Annals of Combinatorics. 2002. Indexada en el MathScNet. Vol. 6 2, pp. 1 - 13

12)Berrizbeitia, P. Deterministic proofs of primality.. (2001). Gaceta de la Real Sociedad de Matemática Española. Artículo Invitado. Vol. 4(2001) No.2, pp. 447 – 456

13)Berry, T; Richard D. Patterson. Implicitization and parametrization of nonsingular cubic surfaces. (2001). COMPUTER AIDED GEOMETRIC DESIGN. . Indexada en el SCI. Vol. 18, pp. 723 - 738

14)Berrizbeitia, P; Berry, T. Generalized strong pseudoprimes tests and applications.. (2000). JOURNAL OF SYMBOLIC COMPUTATION. . Indexada en el SCI. Vol. 30, no2, pp. 151 - 160

15)Berry, T. Continued fractions in hyperelliptic function fields.. (2000) Coding Theory, Cryptography, and Related Areas. "". Vol. . pp. 29 - 41

16)Berry, T. Groebner bases of the ideal of a space curve. (2000) Vol.2, pp. 17 - 27

17)Rosas, Mercedes Helena. "MacMahon symmetric functions, the partition lattice, and Young subgroups.". JOURNAL OF COMBINATORIAL THEORY SERIES A. 2001. Indexada en el SCI. Vol. 96, pp. 325 - 340

18)Rosas, Mercedes Helena. "The Kronecker product of Schur functions indexed by two-row shapes or hook shapes.". JOURNAL OF ALGEBRAIC COMBINATORICS. 2001. Indexada en el SCI. Vol. 14, pp. 153 - 173.

19)Giudici, R.; Olivieri, A.. "Quadratic modulo 2^n Cayley graphs". DISCRETE MATHEMATICS. 2000. Indexada en el SCIENCE CITATION INDEX. Artículo Invitado. Vol. 215, pp. 73 – 79

20)Ordaz, O; Quiroz, D.. "The Erdös-Ginzburg-Ziv Theorem in Abelian non-CyclicGroup". Divulgaciones Matemáticas. 2000. Vol. 8, pp. 113 - 119

21)González, L; Márquez, I; Quiroz, D.. "Hamiltonian Virus-Free Digraphs". Divulgaciones Matemáticas. 2000. Vol. 8, pp. 1 - 13

Listado de Tesis

Trabajos de Grado (Maestría)

Rodríguez, Miguel (Autor(es)). Berrizbeitia, P (Tutor(es)). "Una Prueba Determinista de Primalidad para Números de la forma 5^p - F_p 5^{(p+1)/2} + 1". Título Académico: Magister en Matemáticas. Coordinación Académica: Matemáticas. Nivel Académico: Maestría. Fecha de Defensa: 15 de Julio de 2004

Trabajos de Grado (Licenciatura)

Salerno, A. (Autor(es)). Berrizbeitia, P. (Tutor(es)). "La Ley de Reciprocidad de Eisenstein.". Título Académico: Licenciado en Matemáticas. Coordinación Académica: Matemáticas. Nivel Académico: Licenciatura. Fecha de Defensa: 20 de Julio de 2001

Conferencias Invitadas

Berrizbeitia, P. "Sharpening Primes is in P for a large family of numbers.". Modalidad: Invitada. Future Directions in Algorithmic Number Theory. Palo Alto, California, USA. Marzo 2003

Premios:

Rosas, Mercedes Helena. "Postdoctoral Fellowship". 15 de Mayo de 2003. Institución que otorga: Universidad de Quebec en Montreal. Observaciones: Laboratoire de combinatoire et d'informatique mathématique, l'Université du Québec à Montréal.

Rosas, Mercedes Helena. "Cambridge Philosophical Society bursary award". 01 de Enero de 2001. Institución que otorga: Cambridge Philosophical Society.

Rosas, Mercedes Helena. "Membership/visiting fellowship". 01 de Enero de 2001. Institución que otorga: Isaac Newton Institute, Cambridge University

Proyectos en curso y planes futuros:

En la actualidad el grupo realiza varios proyectos de investigación en el área de primalidad: Por una parte, desde el año 2001, los profesores Berrizbeitia, Berry, Iskra y Olivieri trabajan en un proyecto titulado “buscando primos gigantescos”, que consiste en la implementación de algoritmos muy eficientes que permiten encontrar primos en familias especiales de números. Hasta ahora el primo más grande que se ha encontrado en este proyecto tiene 51.456 dígitos decimales. Para más información sobre este y otros proyectos en curso visite la página del grupo http://www.ma.usb.ve/~gid-24

El grupo cuenta, desde mediados de 2004, con un ayudante de Investigación, el licenciado José Gregorio Fernandes, quien trabaja en la implementación de diversos algoritmos de primalidad. Los algoritmos más eficientes se dirigen a determinar la primalidad de números en familias muy específicas de números. También estamos trabajando en implementaciones de algoritmos de primalidad para familias más generales, en particular en variantes del llamado algoritmo de ciclotomía APR y en los derivados del famoso algoritmo polinomial AKS, denominado así en honor a sus autores Agrawal, Kayal y Saxena, del Instituto de Investigación de Kanpur, India, quienes en agosto de 2002 publicaron un artículo denominado “Primes is in P”, en el que presentaron el primer y hasta ahora único algoritmo determinista de primalidad de complejidad polinomial. En Noviembre del mismo año, el profesor Berrizbeitia publicó un artículo denominado “Sharpening Primes is in P for a large family of numbers”, en el que introdujo una modificación al algoritmo AKS, también determinista pero con elementos aleatorios, que es mucho más rápido que el algoritmo AKS, totalmente determinista para una familia muy grande de enteros. El trabajo de Berrizbeitia ha sido extendido independientemente por Bernstein, un investigador de la universidad de Michigan, en USA y por Mihailescu-Avanzi, investigadores europeos, el primero de los cuales trabaja actualmente en la universidad de Gottingen, en Alemania. Berrizbeitia dirige actualmente la tesis doctoral del licenciado Víctor Ramírez, quien también trabaja en variantes del algoritmo AKS. El tema de primalidad, en sus diferentes matices, ocupa buena parte del trabajo de investigación de la mayoría de los integrantes del grupo. Estamos en proceso de establecer un convenio con la universidad de Calgary, en Canadá, para intercambios, pues con varios profesores del departamento de matemáticas de esa universidad también hemos establecido fuertes vínculos profesionales.