The multiparty multiplication of two polynomially shared values over \mathbb{Z}_q with a public prime number q is an important module in distributed computations. The multiplication protocol of Gennaro, Rabin and Rabin (1998) is considered as the best protocol for this purpose. It requires a complexity of O(n^{2}k log n + nk^2) bit-operations per player, where k is the bit size of the prime q and n is the number of players. The present paper reduces this complexity to O(n^{2}k +nk^2) by using Newton?s classical interpolation formula. The impact of the new method on distributed signatures is outlined.