Re: question: random number in residue number representation

On Feb 1, 10:21 pm, d...@xxxxxxxxxxxxxxxxxxxxxxxx (David Wagner)
wrote:
Herman Rubin wrote:
jiangwu.m...@xxxxxxxxx <jiangwu.m...@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).

Exactly. Actually the problem can be better formulated: to generate
an x such that 0<= x < p_1p_2...p_l for a given l<n.
.