----- Original Message -----
From: "Ben Laurie" <[EMAIL PROTECTED]>
To: <[EMAIL PROTECTED]>
Sent: Wednesday, January 17, 2001 7:18 PM
Subject: Re: BN_rand question
> Marco Russo wrote:
> >
> > I need to generate a random polynomial in Zp, with p very large
(1024-2048
> > bits).
> > Sorry for my math...:-(,
> > but I think that with your method the problem is that the numbers in [0,
> > p-1] are equally likely only if
> > (2^(n - 1))mod p = 0, where n is the number of bits in input to BN_rand
> > (there are 2^(n-1) numbers of
> > n bits, from 10...00 to 11...11).
> > Finding an n such that (2^(n - 1))mod p = 0 is really hard....
> >
> > Another way could be to fill an array A of bits.
>
> What??? That's what BN_rand already does!
Ah ..ok! I thought that the MSD of the number generatated form BN_rand was
1:-(!
Thanks
>
> >
> > for(i = 0; i<numbits(p);i++){
> > if (result of BN_rand is an odd num.)
> > A[i]=1;
> > else
> > A[i]=0;
> > if( number in A > p){
>
> Clearly this can only be true when i == numbits(p)-1.
>
> > A[j]=0 for each i<=j<=numbits(p);
> > break;
> > }
> > }
> >
> > What about this method? I think it's too expansive...
>
> That introduces bias by folding the numbers above p (which there are
> less than p of). A right thing to do is to simply choose a new random
> number if you exceed p. This introduces no bias. Or choose a random
> number with numbits(p)+k in, multiply by p, stretch to 2*numbits(p)+k
> and choose the top numbits(p) bits. Which would introduce almost no
> bias.
>
> Cheers,
>
> Ben.
>
> --
> http://www.apache-ssl.org/ben.html
>
> "There is no limit to what a man can do or how far he can go if he
> doesn't mind who gets the credit." - Robert Woodruff
> ______________________________________________________________________
> OpenSSL Project http://www.openssl.org
> User Support Mailing List [EMAIL PROTECTED]
> Automated List Manager [EMAIL PROTECTED]
>
______________________________________________________________________
OpenSSL Project http://www.openssl.org
User Support Mailing List [EMAIL PROTECTED]
Automated List Manager [EMAIL PROTECTED]
