question: random number in residue number representation

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?

Thanks,

Jiang Wu
.

Relevant Pages

  • Re: question: random number in residue number representation
    ... assume that a random bit generator is free. ... I saw in a paper that r can be generated in residue ... algorithm. ... -- Microsoft voice recognition live demonstration ...
    (sci.crypt)
  • Re: question: random number in residue number representation
    ... Any one know such a random number generator: ... The question is to generate a random number r in residue number ... let's set so double the killer delete select all. ... -- Microsoft voice recognition live demonstration ...
    (sci.crypt)
  • Re: rand() pattern in texture?
    ... > Phil Carmody wrote: ... > programming implementation of a given algorithm. ... > Looks to me like the period of the single lowest bit is 17, ... > as is the period of the generator itself. ...
    (sci.math)
  • Re: famous literature
    ... Before I describe the algorithm, ... there is an important mathematical function - xor - that has an ... will generate random seeds. ... the run length random number generator. ...
    (sci.crypt)
  • Re: bilinear pairing between special groups
    ... >> Remainder Theorem to find a generator for this group. ... pp. 6 of that is the proof that there is a polynomial time algorithm ... >> Solving the GDLP in an arbitrary cyclic group G of order n is ... >could be done efficiently, but what happens with the bilinear pairing, ...
    (sci.math)