- Computer Sciences
Professor Eric Bach is interested in how one uses computers to efficiently solve algebraic and number-theoretic problems (example: how does one tell if a 100-digit number is prime without examining all possible factors?). These problems have intrinsic mathematical interest, as well as applications to random number generation, codes for reliable and secure information transmission, computer algebra, and other areas. Bach is also interested in applying probability theory to the design and analysis of algorithms. For example, if a large number is composite, it can be proved so by a simple test that uses an auxiliary number, called a "witness." In practice, one usually finds a witness by direct search among the small primes. This leads to the following natural question: how large is the least witness, as a function of the number tested? In recent work, we have given an accurate heuristic model, based on probabilistic assumptions, that allows this, and similar questions, to be answered.