Classification of quadratic iteration graphs
This paper was written for the class 18.310 (Principles of Discrete Applied Mathematics) based on research I did with Prof. Abhinav Kumar over the summer of 2010. The paper’s target audience is advanced undergraduates who have been exposed to the ideas of group theory. A reader well-versed in basic algebra can skip the first few pages, but may want to review the elementary number theory section.
The basic theory of iteration graphs are explained, and quadratic iteration graphs of the form f(x) = x2 + c modulo prime p are classified for c = 0. As an application, the structure of the iteration graph for f(x) = x2 is used to explain the operation of the Tonelli square root algorithm.
Download the paper: (PDF)