We will discuss a deterministic algorithm that, given a composite number N and a target order D ≥ N^{1/6}, runs in time D^{1/2+o(1)} and finds either an element of multiplicative order at least D, or a nontrivial factor of N. Our algorithm improves upon an algorithm of Hittmeir (2018), who gave an algorithm with similar guarantees under stronger assumptions. Hittmeir's algorithm played a crucial role in the recent breakthrough deterministic integer factorization algorithms of Hittmeir and Harvey (2020, 2021).Based on a joint work with Ziv Oznovich.
Short Bio: Ben Lee Volk is a member of the faculty at the School of Computer Science at Reichman University in Israel. He did his PhD at Tel Aviv University and spent his postdoc years at Caltech and UT Austin before moving to Reichman. His research interests are broadly in computational complexity, with a particular focus on algebraic complexity, algorithms for algebraic problems, error correcting codes and pseudorandomness.
