CWI Cryptology Group

Abstract: We give a brief survey of recent results related to the sum-product problem which dates back to work of Erdos and Szemeredi (1983), where it is shown that for any set A of real numbers, at least one of the sets A+A = {a_1 + a_2 : a_1,a_2 in A} and A A = {a_1 a_2 : a_1,a_2 in A} is large. More recently, Bourgain, Katz and Tao (2006) obtained similar results for sets A in prime finite fields. We outline these and several other recent results in this area and also present a diverse scope of their applications to several other problems. Finally we mention several open problems, some of which are motivated by applications to cryptography.