Finding powers of multiple array pairs
General Design

The pattern foreach...puts... means that each iteration performs IO. Because IO is slow and blocks writing the results of each multiplication to an output array and then batching the IO by writing the output array all at once is likely to improve performance.

Algorithm

From a pure algorithmic standpoint, using modular powers may significantly reduce computation. This website provides this example:

Let us compute 1143 (mod 13). As we saw before we start with squaring this number:

112 (mod 13) = 121 (mod 13) = 4 (mod 13)

114 (mod 13) = (112)2 (mod 13) = 42 (mod 13) = 16 (mod 13) = 3 (mod 13)

118 (mod 13) = (114)2 (mod 13) = 32 (mod 13) = 9 (mod 13)

1116 (mod 13) = (118)2 (mod 13) = 92 (mod 13) = 81 (mod 13) = 3 (mod 13)

1132 (mod 13) = (1116)2 (mod 13) = 32 (mod 13) =  9 (mod 13)


Putting this together (remember that 43 = 32 + 8 + 2 +1), we get

 1143 (mod 13) = 11 * 4 * 9 * 9 (mod 13)

Now we do our usual modular multiplication:
11 * 4 * 9 * 9 (mod 13) = 44 * 81 (mod 13) = 5 * 3 (mod 13) = 2 (mod 13).


When tackling a numeric problem and throughput matters, a good place to start is with assuming that the fundamental problem has already been solved and attempting to reduce the specific problem to an existing numeric algorithm. It is hard to embody performant mathematics into code without first knowing what is performant.