HONG KONG BAPTIST UNIVERSITY
FACULTY OF SCIENCE
Department of Computer Science and Department of Mathematics
Joint Distinguished Lecture
Some Mysteries of Multiplication, and How to Generate Random Factored Integers
Prof. Richard P. Brent
Mathematical Sciences Institute
Australian National University
Date: February 6, 2015 (Friday)
Time: 2:30 - 4:00 pm
Venue: RRS905, Sir Run Run Shaw Building, Ho Sin Hang Campus
Let M (n) be the number of distinct entries in the multiplication table for integers smaller than n. The order of magnitude of M (n) was established in a series of papers by various authors, starting with Erd ӧs (1950) and ending with Ford (2008), but an asymptotic formula for M (n) is still unknown. After describing some of the history of M (n) I will consider algorithms for computing M (n) exactly for moderate values of n, and Monte Carlo algorithms for estimating M (n) accurately for large n. This leads to consideration of algorithms, due to Bach (1985–88) and Kalai (2003), for generating random factored integers – integers r that are uniformly distributed in a given interval, together with the complete prime factorisation of r. This is joint work with Carl Pomerance.
In 1978, Richard Brent was appointed Foundation Professor of Computer Science at ANU, and in 1985, he became Professor and Head of the Computer Sciences Laboratory in the Research School of Physical Sciences at ANU. In 1998, he moved to Oxford as Statutory Professor of Computing Science and Fellow of St Hugh's College. In March 2005, he returned to ANU to take up a 5-year position as an ARC Federation Fellow in the Mathematical Sciences Institute (MSI) and the Research School of Information Sciences and Engineering. In March 2010, he became a Distinguished Professor with a joint appointment in MSI and the School of Computer Science. Since Sept. 2011, he has been an Emeritus Professor at ANU and a Conjoint Professor at the University of Newcastle. He is a Fellow of the ACM, IEEE, SIAM, the Australian Academy of Science, and various other professional bodies.
********* ALL INTERESTED ARE WELCOME ***********
(For enquiry, please contact Computer Science Department at 3411 2385)
Department of Computer Science, Hong Kong Baptist University