Re: question: random number in residue number representation


In article <26f85cd7-aded-45f1-bab3-61e530cc2516@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
jiangwu.mail@xxxxxxxxx <jiangwu.mail@xxxxxxxxx> wrote:
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?

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.

--
This address is for information only. I do not claim that these views
are those of the Statistics Department or of Purdue University.
Herman Rubin, Department of Statistics, Purdue University
hrubin@xxxxxxxxxxxxxxx Phone: (765)494-6054 FAX: (765)494-0558
.

Relevant Pages

  • Re: An example of a complete but undecidable theory
    ... >there is an algorithm for determining, for any sentence A, whether or ... set of numbers which correspond to the negation of a theorem ... are those of the Statistics Department or of Purdue University. ... Herman Rubin, Department of Statistics, Purdue University ...
    (sci.math)
  • Re: An example of a complete but undecidable theory
    ... >there is an algorithm for determining, for any sentence A, whether or ... set of numbers which correspond to the negation of a theorem ... are those of the Statistics Department or of Purdue University. ... Herman Rubin, Department of Statistics, Purdue University ...
    (sci.logic)
  • Re: Exchange algorithm (Remez or Parks-McClellan)
    ... are those of the Statistics Department or of Purdue University. ... Herman Rubin, Department of Statistics, Purdue University ... minimax polynomial approximations up to 8 parameters and degree 15 ... regression with my algorithm posted above. ...
    (sci.math.num-analysis)
  • Re: languages for CAS .. was: Re: Which is the best CAS
    ... algorithm in the "Category" (warning: category is not used in the ... C or Fortran is easier to understand. ... are those of the Statistics Department or of Purdue University. ... Herman Rubin, Department of Statistics, Purdue University ...
    (sci.math.symbolic)
  • Re: Why to call it pseudorandom?
    ... predictive power when tested against the algorithm. ... I do not claim that these views are those of the Statistics Department or of Purdue University. ...
    (sci.math)