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?

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
10
  • $\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, 2018 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, 2018 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, 2018 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, 2018 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, 2018 at 14:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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