Fast Chinese Remaindering via Product Trees

Product trees are a simple data structure that, broadly speaking, allows dealing with the product of a large number of (typically coprime) integers, or more generally elements of a Euclidean ring.

This is particularly useful for efficient simultaneous modular reduction, i.e. computing $x\mathbin{\text{mod}} m_i$ for a large number of moduli $m_i$ at the same time for a fixed $x$, and the inverse operation thereof, i.e. modular reconstruction (also known as “Chinese Remaindering”).

The algorithms formalised are adapted from the book “Modern Computer Algebra” by von zur Gathen and Gerhard.