Re: question: random number in residue number representation

"jiangwu.mail@xxxxxxxxx" <jiangwu.mail@xxxxxxxxx> writes:
Hi,

Any one know such a random number generator:

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). We
assume that a random bit generator is free.

It's straightforward to use the random bit generator to generate r
such that 0<=r<=b, and compute r_1=r mod p_1,.... , but it would take
O((log g)^2) time. I saw in a paper that r can be generated in residue
number representation and 0<=r<=b in O(log g) time using a proprietary
algorithm. Any one knows how it can be done?

Would O(log(g).loglog(g)) do? That should be pretty easy.
Dan Bernstein's work contains many of the tricks required
for such big-Oh reduction.

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

Relevant Pages