Eric Bach is an American

computer scientist A computer scientist is a scientist who specializes in the academic study of computer science. Computer scientists typically work on the theoretical side of computation. Although computer scientists can also focus their work and research on ...

who has made contributions to

computational number theory In mathematics and computer science, computational number theory, also known as algorithmic number theory, is the study of computational methods for investigating and solving problems in number theory and arithmetic geometry, including algorithm ...

. Bach completed his undergraduate studies at the

University of Michigan, Ann Arbor The University of Michigan (U-M, U of M, or Michigan) is a public research university in Ann Arbor, Michigan, United States. Founded in 1817, it is the oldest institution of higher education in the state. The University of Michigan is one of th ...

, and got his Ph.D. in computer science from the

University of California, Berkeley The University of California, Berkeley (UC Berkeley, Berkeley, Cal, or California), is a Public university, public Land-grant university, land-grant research university in Berkeley, California, United States. Founded in 1868 and named after t ...

, in 1984 under the supervision of

Manuel Blum Manuel Blum (born 26 April 1938) is a Venezuelan-born American computer scientist who received the Turing Award in 1995 "In recognition of his contributions to the foundations of computational complexity theory and its application to cryptography ...

. He is currently a professor at the Computer Science Department,

University of Wisconsin–Madison The University of Wisconsin–Madison (University of Wisconsin, Wisconsin, UW, UW–Madison, or simply Madison) is a public land-grant research university in Madison, Wisconsin, United States. It was founded in 1848 when Wisconsin achieved st ...

. Among other work, he gave explicit bounds for the

Chebotarev density theorem The Chebotarev density theorem in algebraic number theory describes statistically the splitting of primes in a given Galois extension ''K'' of the field \mathbb of rational numbers. Generally speaking, a prime integer will factor into several id ...

, which imply that if one assumes the

generalized Riemann hypothesis The Riemann hypothesis is one of the most important conjectures in mathematics. It is a statement about the zeros of the Riemann zeta function. Various geometrical and arithmetical objects can be described by so-called global ''L''-functions, whi ...

then

\left(\mathbb/n\mathbb\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 The Miller–Rabin primality test or Rabin–Miller primality test is a probabilistic primality test: an algorithm which determines whether a given number is likely to be prime, similar to the Fermat primality test and the Solovay–Strassen pr ...

. Bach also did some of the first work on pinning down the actual expected run-time of the Pollard rho method where previous work relied on heuristic estimates and empirical data. He is the namesake of

Bach's algorithm Bach's algorithm is a probabilistic polynomial time algorithm for generating random numbers along with their factorizations. It was published by Eric Bach in 1988. No algorithm is known that efficiently factors random numbers, so the straightforw ...

for generating random factored numbers.

References

American computer scientists Living people University of Michigan alumni UC Berkeley College of Engineering alumni University of Wisconsin–Madison faculty Year of birth missing (living people) American number theorists 20th-century American scientists 21st-century American scientists {{US-mathematician-stub