Fast Arithmetics Using Chinese Remaindering

In this paper, some issues concerning the Chinese remaindering representation are discussed. A new converting method, which is an efficient probabilistic algorithm based on a recent result of von zur Gathen and Shparlinski [J. von zur Gathen, I. Shparlinski, GCD of random linear forms, Algorithmica 46 (2006) 137-148], is described. An efficient refinement of the NC^1 division algorithm of Chiu, Davida and Litow [A. Chiu, G. Davida, B. Litow, Division in logspace-uniform NC^1, Theoret. Informatics Appl. 35 (2001) 259-275] is given, where the number of moduli is reduced by a factor of logn.