Re: question: random number in residue number representation

"jiangwu.mail@xxxxxxxxx" <jiangwu.mail@xxxxxxxxx> writes:
On Feb 5, 1:48 pm, hru...@xxxxxxxxxxxxxxxxxxxx (Herman Rubin) wrote:
In article <whocares> jiangwu.m...@xxxxxxxxx <jiangwu.m...@xxxxxxxxx> wrote:
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.

In this case, x is determined by its residues mod p_1, ..., p_l.

I do not see any solution other than getting the residues
mod p_{l+1}, ..., p_n from the result of those. One way
of doing this, if the same p's occur often, is to preset
the constants needed to carry out the computation.
You mean in the case that p_i=p_j? but all p_i, p_j need to be coprime
here.

One thing that strikes me is that you can arbitrarily chose r_i for
at least half of the p_i, and then it's just a matter of finding
the x_j for the other p_j that make the final total congruence hold.

Phil
--
Dear aunt, let's set so double the killer delete select all.
-- Microsoft voice recognition live demonstration
.