Let us have about 100 or so random integers such as:
$$ A_1 = 1234123\\ A_2 = 13713\\ A_3 = 41232\\ A_4 = 123\\ ...$$
Now I want to find an efficient way to get the modulus
$(A_1 \times A_2 \times A_3 ..... \times A_n ) \mod B$
where B is an integer such as 123. Is there an efficient algorithm to do this? Note, that we can't simply multiply all the numbers together because we assume we are using machine precision integers and we would get an overflow.
To put it in a more mathematically precise way: Find an algorithm to find the solution of this product where not step in the algorithm contains numbers higher than the square of any of the values of $A_n$.
One method if $B^2<N$ ($N$ is your precision) is to first set
$$A_i'=(A_i \bmod B)$$
to be the remainder when $A_i$ is divided by $B$. Then, define
$$P_i\equiv \prod_{j=1}^i A_j' \bmod B.$$
We can calculate $P_i$ as $P_{i-1}\cdot A_i'\bmod B$ without employing any calculations with numbers larger than $B^2$, and $P_{n}$ (if you have $n$ multiplicands) is your answer, while $P_1$ is simply $A_1'$. So, you can calculate this product in $O(n)$ time by essentially multiplying them one at a time and taking the product $\bmod B$ after each calculation, without dealing with any numbers $>B^2$.