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!
>
> 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]
