I have a large number which I suspect may be a private RSA key (although its size, at 613 bits, seems a bit unorthodox).

I have started to run a factorization algorithm on it, and after a few hours it still has not found any factors. But I wouldn't want to keep the algorithm running for a couple more days (or pay for a few EC2 instances to run the factorization on) only to find out that it is simply the product of three or more somewhat large prime numbers.

So, I was wondering if there was a way (even theoretical!) to check if that number was indeed the product of two prime numbers without actually having to factorize it.

  • 2
    $\begingroup$ Welcome to Cryptography. You can use a probabilistic primality test as Rabin-Miller which are much faster than factorization. However, this will give you only composite information truly and primeness with a probability. There is also a deterministic primality test, though it is slower than Rabin-Miller. Note: is this homework or CTF? $\endgroup$ – kelalaka Mar 20 at 16:33
  • $\begingroup$ CTF. Thanks! Will look into the tests you mentioned. $\endgroup$ – Robert T. Tusk Mar 20 at 16:46
  • 1
    $\begingroup$ Not that I'm aware of. Generally we want to do a quick look for small factors, then a primality test (M-R or BPSW). After that, we might want to do some better methods for small factors (e.g. Rho-Brent, P-1, ramped up ECM or possibly deterministic ECM (Chelli)). If that fails, then we're stuck -- it is composite and doesn't seem to have any small factors, so we'd have to fully factor to know for sure. $\endgroup$ – DanaJ Mar 20 at 17:16
  • 1
    $\begingroup$ What do you mean by you "suspect [the number] may be a private RSA key"? Generally the (full) private key is two numbers, a private exponent and a modulus. Based on the context I assume you mean you think it's an RSA modulus but it would be helpful to clarify. $\endgroup$ – puzzlepalace Mar 20 at 17:39
  • 1
    $\begingroup$ There is an answer by Terry Tao on mathoverflow to the question "how hard is it to compute the number of prime factors of a given integer"; The conclusion seems to be "probably as hard as factoring". Another answer there points out that determining whether or not a number has an even or odd number of prime factors is also difficult. $\endgroup$ – Ella Rose Mar 20 at 18:16

Your Answer

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

Browse other questions tagged or ask your own question.