A Constructive Proof of Jacobi's Identity for the Sum of Two Squares

We present a constructive proof of Jacobi’s identity for the sum of two squares. We present a combinatorial proof of the Jacobi Triple Product and combine with a proof of Hirschhorn to define an algorithm. The input is a factorization $n=dN$ with $d\equiv 1\mathrm{m}\mathrm{o}\mathrm{d}4$ plus two bits of data, and whose output is either another factorization $n=d^{\mathrm{\prime }}{N}^{\mathrm{\prime }}$ and $d^{\mathrm{\prime }}\equiv 3\mathrm{m}\mathrm{o}\mathrm{d}4$ with two more bits of data, or a pair of integers whose squares sum to $n$. We phrase this algorithm in terms of integer partitions and matchings on an infinite graph.