It depends. (A(x) mod Q(x)) * (B(x) mod Q(x)) = (A(x) * B(x)) mod Q(x) If the chunk size N is known beforehand you can pre-calculate x^N mod Q(x), so appendin

It depends. (A(x) mod Q(x)) * (B(x) mod Q(x)) = (A(x) * B(x)) mod Q(x) If the chunk size N is known beforehand you can pre-calculate x^N mod Q(x), so appending N zeros will be an O(1) multiplication. Only if the chunk size is not known, you have to calculate x^N mod Q(x) via modular exponentiation, which is O(log n). But you only need to do this once, and then you can reuse the value for all subsequent chunks.