Re: question: random number in residue number representation

In article <dfe03304-b08c-48ed-bac9-865aeba6b05d@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
jiangwu.mail@xxxxxxxxx <jiangwu.mail@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.
--
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: On comp.soft-sys.math.mathematica being moderated [Re: Mathematica problem - generate fi
    ... or perhaps looks at each poster before the first ... posting to make sure it is a real person. ... are those of the Statistics Department or of Purdue University. ... Herman Rubin, Department of Statistics, Purdue University ...
    (sci.math.symbolic)
  • Re: question: random number in residue number representation
    ... the poster asked to generate a random x in approximately the range ... I do not see any solution other than getting the residues ... are those of the Statistics Department or of Purdue University. ... Herman Rubin, Department of Statistics, Purdue University ...
    (sci.crypt)
  • Re: Turmeric!
    ... But since the cardiology unit was supposed to show how GEVALDIG tPA ... After all, BUSINESS IS BUSINESS! ... > are those of the Statistics Department or of Purdue University. ...
    (soc.culture.jewish.moderated)
  • Re: Acceptability of different standards [was Re: On departing SCJM]
    ... absolutely no relationship with Judaism. ... I consider to transgress Shabbath. ... are those of the Statistics Department or of Purdue University. ... Herman Rubin, Department of Statistics, Purdue University ...
    (soc.culture.jewish.moderated)
  • Re: Development of computer analysis systems
    ... finite elements program would run much much faster and what was taking one ... packages do arithmetic may even be worse than the way I ... are those of the Statistics Department or of Purdue University. ... Herman Rubin, Department of Statistics, Purdue University ...
    (sci.math.symbolic)