We give a natural parameterization of the N��ron-Severi group of a product $A = E\times E'$ of two elliptic curves in terms of quadratic forms. As an application, we determine (in the non-CM case) whether $A$ contains a smooth curve of any fixed genus. We also determine whether $A$ admits a very ample line bundle of any fixed degree. In particular, we determine which of these abelian surfaces embed in $\mathbb{P}^4$, i.e. which come from the Horrocks-Mumford bundle.

28 pages; revised introduction and added Section 5