New Analysis of the Factor Refinement Algorithm with Applications

Abstract: In this talk I will discuss a new, simple characterization of the output of the Factor Refinement Algorithm, formally introduced and analyzed by Bach, Driscoll, and Shallit in 1993. Our characterization relies only on basic linear algebra. As applications, we obtain new relations between computing the square-free decomposition of an integer, Euler’s totient function, the radical of an integer, and some other multiplicative functions. While some of the above connections were already established in the literature, we believe that our contribution makes them simpler and more explicit.

Based on Joint work with Dr. Ilya Volkovich