Seminar on Friday 25th at 1:30pm.
We present new algorithms for primality proving, improving the cyclotomic primality proving algorithms, by decreasing the running time the heuristic complexity of primality proving is decreased from log^3 n*(log log n)^(O(1)) to O(log^3 n/log log log n) thanks to the Gentry-Szydlo algorithm used in Gauss, or Jacobi sum computations.
An algorithm factoring an integer n in quasi-polynomial time using only an oracle which outputs the existence of a root modulo n of an integer polynomial is obtained by the same technique.
This algorithm does not require the value of n, and allows new cryptanalytic applications.
Campus de la Plaine, NO building, 8th floor, (Salle Rotule)