Re: rsa key generation question

kaskati2003@xxxxxxxxx wrote: 
Hello all,

I have a question about RSA key generation. Suppose m is a big random
number and K is a fixed constant. Is there an algorithm to generate RSA
keys so that the RSA modulus n is in the vicinity of m by K. e.g. (m-K
< n < m+K).

Sure. Just pick a random prime p in the range sqrt((m+K)/2)..sqrt(m+K). Then pick a random prime q in the range (m-K)/p..(m+K)/p. I've done this with m near a power of 2 and K at least m*2**-16, to get an n that starts with specific binary digits.

If there is any, what is the complexity of this algorithm compared with
the complexity of standard RSA key generation?

Any answer or showing any relevant references is highly appreciated. 

--Mike Amling
.

Loading