About rsa challenge numbers
- For a rsa challenge numbers N = pq where q > p what will be the range of floor value of q/p. As far for known factored rsa numbers what is the floor value of q/p and is there any idea around what range they choose.Can anyone guide me. Since bit sizes of factors are same so it will be in the range of 0 to 10 Am i correct.
> For a rsa challenge numbers N = pq where q > p what will be the range ofYou can easily check this yourself -- just have a look at
> floor value of q/p. As far for known factored rsa numbers what is the
> floor value of q/p and is there any idea around what range they
http://en.wikipedia.org/wiki/RSA_numbers and calculate the ratios.
A quick looks suggests that the floor of q/p is most often equal to 1,
with 2 appearing a few times. The sole exception is RSA-129 (ratio
slightly smaller than 10), which was actually not part of the
RSA Factoring Challenge.
Since they didn't "choose" any specific ratio in advance, it's not really
possible to have "any idea" regarding its value for the unknown numbers.
However, if we follow your assumption:
> Since bit sizes of factors are same so it will be in the range of 0 towe can be sure that floor(q/p) = 1. If the bit-sizes of the factors are
the same (say, N bits), the minimum possible value of p is 2^(N-1)
and the maximum value of q is (2^N - 1). Thus, q/p <= 2 - 1/2^(N-1) < 2,
which is enough to complete the proof.