Loading ...
Sorry, an error occurred while loading the content.
 

About rsa challenge numbers

Expand Messages
  • kad
    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
    Message 1 of 2 , Aug 4, 2012
      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.
    • Peter Kosinar
      ... You can easily check this yourself -- just have a look at http://en.wikipedia.org/wiki/RSA_numbers and calculate the ratios. A quick looks suggests that
      Message 2 of 2 , Aug 4, 2012
        > 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.

        You can easily check this yourself -- just have a look at
        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 to
        > 10.

        we 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.

        Peter
      Your message has been successfully submitted and would be delivered to recipients shortly.