Do, 15.12.2016 15:00
Group Seminar: QMC: A babystep-giantstep method for faster deterministic integer factorization
Location: MT 130
In 1977, Volker Strassen presented a deterministic and rigorous algorithm for solving the problem to compute the prime factorization of natural numbers. His approach is based on fast polynomial arithmetic techniques and has been state of the art for the last fourty years. In this talk, we discuss the core ideas of a method for improving the runtime complexity bound by a superpolynomial factor.