// Workers AI · dad joke modeWho's Eric Bach's favorite composer? Bach to basics.

Eric Bach
Born	November, Chicago, Illinois, U.S.
Alma mater	University of California - Berkeley University of Michigan
Scientific career
Fields	Computer Science
Institutions	University of Wisconsin - Madison
Doctoral advisor	Manuel Blum
Doctoral students	John Watrous Victor Shoup

Eric Bach is an American computer scientist who has made contributions to computational number theory.

Bach completed his undergraduate studies at the University of Michigan, Ann Arbor, and got his Ph.D. in computer science from the University of California, Berkeley, in 1984 under the supervision of Manuel Blum. He is currently a professor at the Computer Science Department, University of Wisconsin–Madison.

Research

Among other work, he gave explicit bounds for the Chebotarev density theorem, which imply that if one assumes the generalized Riemann hypothesis then $\left(\mathbb {Z} /n\mathbb {Z} \right)^{*}$ is generated by its elements smaller than 2(log n)². This result shows that the generalized Riemann hypothesis implies tight bounds for the necessary run-time of the deterministic version of the Miller–Rabin primality test.

In 1991, Bach proved that if you start Pollard's rho algorithm with random values x and y and iterate k times, the probability that it successfully discovers a prime factor p is at least ${\binom {k}{2}}/p+O(p^{-{\frac {3}{2}}})$. As a result, he also proved that the probability of success obeys the lower bound $\Omega ((\log ^{2}p)/p)$.

He is the namesake of Bach's algorithm for generating random factored numbers.

External links

• Official website