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

Re: [PrimeNumbers] About rsa challenge numbers

Expand Messages
  • 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 1 of 2 , Aug 4, 2012
    • 0 Attachment
      > 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.