1
$\begingroup$

Is there a way to find out the first few digits of the factors of the RSA numbers (RSA-1024 or RSA-2048)?

I do not want to get all the digits but only first 4-5 digits. My question is thus more precisely:

Is there a known, efficient, classical algorithm, that given a composite number, outputs the 4-5 most significant decimal digits of one of the prime factors of this number?

$\endgroup$
4
$\begingroup$

I do not think this is a practical possibility. In order to get the 4-5 most significant bits, the bits of lower significance must be known. This is due to the manner in which numbers are multiplied. The most significant bits of the product do not depend solely on the most significant bits of the factors. Bits of lower significance may have an effect too due to the propagation of carry bits up the product as partial products are summed. Even with some look-ahead optimizations the bits of lower significance would still need to be known. The best I could see would be a probabilistic scheme in which k>5 bits would would be attempted to be solved and the result would be probabilistically correct with some chance as a function of k.

$\endgroup$
  • $\begingroup$ Would this method be efficient- i,e would it run in polynomial time? Also can the probability of error be reduced to an arbitrarily low value with a polynomial runtime? In other words is this method in the complexity class BPP? $\endgroup$ – rajeesh Mar 7 '18 at 13:40
  • $\begingroup$ I've not tried anything of this sort previously, however my intuition is that it would be doable in polynomial time. If you've got an RSA key of 1024 or 2048 bits, I would anticipate that the top 45 bits, implying k = 40, would be sufficient for the probabilistic aspect of the correctness. $\endgroup$ – Ken Goss Mar 7 '18 at 13:48
  • $\begingroup$ This method would not work however for Mersenne Primes due to their special form. I just realized that. $\endgroup$ – Ken Goss Mar 7 '18 at 13:51
  • $\begingroup$ Thanks, I found it strange that no one has tried it out on RSA numbers to figure out the first few digits. $\endgroup$ – rajeesh Mar 7 '18 at 14:01
  • 1
    $\begingroup$ Loads of people have tried loads of things. This problem is one part of the P=NP question/debate. This problem is assumed to be NP, and NP is assumed to not equal P. Factoring integers being in P or P=NP both seem unlikely given the amount of research gone into their investigation, but neither has a proof of their non-equivalence been forthcoming given the copious amounts of research. $\endgroup$ – Ken Goss Mar 7 '18 at 14:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.