A Number Theoretic Memory Bounded Function and Its Applications

Memory bounded functions have been designed to combat email spams in a sequence of papers. The cost of computing the functions is usually dominated by random walks over large tables that cannot be put in CPU cache. In this paper, we propose a simple number theoretic way of generating such tables based on exponentiations of sparse polynomials modulo sparse irreducible polynomials over finite fields. We also present a formal definition of memory bounded functions that can be used to construct such tables.