6
$\begingroup$

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.

Improve this question
$\endgroup$
11
  • 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, 2019 at 16:33
  • 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, 2019 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, 2019 at 17:39
  • 1
    $\begingroup$ Run ECM long enough to get confidence that the factors must be at least a certain size? Note that an RSA modulus is not necessarily the product of only two primes. $\endgroup$
    – Squeamish Ossifrage
    Mar 20, 2019 at 18:06
  • 3
    $\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, 2019 at 18:16

3 Answers 3

Reset to default
5
$\begingroup$

Given a 613-bit integer, it is easy to check that it is composite (and we assume that's been done). It can be hard to factor, but that's feasible with GNFS, including with ready-made tools (see Luke Valenta, Shaanan Cohney, Alex Liao, Joshua Fried, Satya Bodduluri, Nadia Heninger's Factoring as a Service), and that's one sure way to demonstrate how many factors it has.

We can do better! We can use Lenstra's ECM repeatedly, with parameters and runtime tuned to find factors less than about 205 bits. That's within reach of the best current implementations, see Paul Zimmermann's list of ECM factoring records. If that fails, then it is a very strong indication that there is no factor 205-bit or less, thus there must be only two factors (for the product of three or more 205-bit integers has at least 613 bits). If that succeeds, we can test the primality and/or factor the rest.

I believe the tool of choice is GMP-ECM.

Edit: That is not generalizable to much larger integers. Starting about 800 bits, it becomes quite hard to tell apart those with two factors, and those with three factors of about equal size.

Improve this answer
$\endgroup$
0
3
$\begingroup$

Without factoring it, you can only tell if the number of factors is one, or greater than one.

What you ask is not possible unless at least one of the prime factors of a composite integer is small enough that the integer can be partially factored. If at least one factor is small, then after revealing that prime, a fast primality test could be used on the remaining integer to test if it is still composite and, if it is, you know that there are at least three primes. If, however, all the prime factors are large and random, then you will be unable to determine how many factors there are without completely factoring it.

If you have a large, random number and want to test if it is an RSA modulus or just something random, you can run basic, fast factorization algorithms on it like trial division and Pollard rho. Chances are, for a random integer, there will be at least a few small factors. If you see that one of them is 7 (for example), you can be pretty sure that it's not an RSA modulus, at least not from any sane implementation of RSA.

Edit: You specified a 613-bit integer. That is small enough that it is possible to tell if it is the product of two or three primes. See fgrieu's answer for more details on that. My answer applies only to the generic question about whether or not it's possible to check if an arbitrary integer is the product of two primes.

Improve this answer
$\endgroup$
1
  • 3
    $\begingroup$ It is possible to do better: in a nutshell, if there was 3 factors, one would be small enough that ECM pulls it; thus if ECM fails, there must be 2 factors. $\endgroup$
    – fgrieu ♦
    Sep 9, 2019 at 6:05
-1
$\begingroup$

You can test whether the number is composite without knowing its factors by using Fermat's Lesser Theorem: If $p$ is prime, $a^{p-1} \equiv 1 \bmod N$, so if $a^{p-1} \not\equiv 1$, you know the number is composite.

Here's an example.

https://youtu.be/keXQRT4aB1E?list=PLKXdxQAT3tCssgaWOy5vKXAR4WTPpRVYK

Some posters noted that this only tells you if it's composite, not whether it's the product of two primes, which is true. But note that you don't need a RSA modulus to be a product of two primes, and there are good reasons for using the product of three or more primes for a RSA modulus.

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ But this only reveals that a number is a composite but we don't know that it woud be a semi-prime, it could also be a number that has a lot of prime factors. $\endgroup$
    – AleksanderCH
    Sep 9, 2019 at 23:26
  • 1
    $\begingroup$ Right about the $p-1$, fixed. $\endgroup$
    – Jeff Suzuki
    Sep 10, 2019 at 12:15

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.