Re: question: random number in residue number representation

Herman Rubin wrote:
jiangwu.mail@xxxxxxxxx <jiangwu.mail@xxxxxxxxx> wrote:
Let p_1,...,p_n be n prime numbers. Let g=p_1p_2...p_n. Any number
0<=x<=g can be represented as x_1,...,x_n, where x_i=x mod p_i.

The question is to generate a random number r in residue number
representation (r_1,...,r_n) and 0<= r <=b where b \approx sqrt(g).

Just generate separately 0 <= x_i < p_i. This can be done
in time O(log p_i), and so one gets O(log g) altogether.

But that generates a random x in the range 0 <= x < g, whereas
the poster asked to generate a random x in approximately the range
0 <= x <= sqrt(g).
.