-1
$\begingroup$

my PC found a factor for (2^2048)-1 in under a second...so does that make RSA-2048 less secure right? i used prime 95. and actually i am kinda curious how it found a factor so fast? i can even factor 2^131072 in less than 5 minutes..? enter image description here

$\endgroup$
  • $\begingroup$ Please learn to write in $\LaTeX$/MathJax. $\endgroup$ – kelalaka Oct 30 '19 at 17:38
  • 3
    $\begingroup$ I can factor $2^{131072}$ in my head in rather less than 5 minutes, if I don't have to explicitly list every prime factor... $\endgroup$ – poncho Oct 30 '19 at 18:02
  • 3
    $\begingroup$ Are you also Ömer Enes Özmen. If so, can merge your accounts. $\endgroup$ – kelalaka Oct 30 '19 at 19:12
8
$\begingroup$

my PC found a factor for (2^2048)-1 in under a second...so does that make RSA-2048 less secure right?

No. Factoring numbers with special forms like that is easy.

You have a Mersenne number, $n = 2^e - 1$, whose exponent $e = 2048$ is composite. Whenever $e = u v$, we have $2^u - 1 \mid (2^u)^v - 1 = 2^e - 1$, since in general $x - 1 \mid x^k - 1$. (Proof: Write out $(x - 1)(x^{k - 1} + x^{k - 2} + \dotsb + x + 1)$.) So, for example, the following are all obviously factors of $2^{2048} - 1$:

  • $2^2 - 1 = 3$
  • $2^4 - 1 = 15 = 3\cdot 5$
  • $2^8 - 1 = 255 = 3\cdot 5\cdot 17$
  • $2^{16} - 1 = 65535 = 3\cdot 5\cdot 17\cdot 257$
  • $2^{32} - 1 = 4294967295 = 3\cdot 5\cdot 17\cdot 257\cdot 65537$

Indeed, in general, for $x^{2k} - 1$, we have $\bigl((x^k)^2 - 1\bigr)/(x^k - 1) = x^k + 1$, so we can reduce $2^{2048} - 1 = 2^{2^{10}} - 1$ to a product of Fermat numbers, which are numbers of the form $2^{2^t} + 1$:

\begin{align*} 2^{2048} - 1 &= (2^{1024} + 1) (2^{1024} - 1) \\ &= (2^{1024} + 1) (2^{512} + 1) (2^{512} - 1) \\ &\vdots \\ &= (2^{1024} + 1) (2^{512} + 1) \dotsm (2^2 + 1) (2^1 + 1). \end{align*}

The only prime Fermat numbers known are 3, 5, 17, 257, and 65537; the remaining factors here are known to be composite.

The ninth Fermat number, $2^{2^9} + 1 = 2^{512} + 1$, was factored in 1990 using the special number field sieve (SNFS), and the tenth, $2^{2^{10}} + 1 = 2^{1024} + 1$, was factored in 1995 using the elliptic curve method (ECM), according to Richard Brent's retrospective. I don't know what algorithm your software uses, but there are enough small factors that it is entirely plausible for software on a laptop today to identify most of them—the number it printed has the two smallest factors of $F_{10} = 2^{1024} + 1$, namely 45 592 577 and 6 487 031 809; the smallest factor of $F_9 = 2^{512} + 1$, namely 2 424 833; and the smallest factor of $F_6 = 2^{64} + 1$, namely 274 177.

In contrast, when $n$ is a product of two uniform random 1024-bit prime numbers, or nearly uniform random, then it's hard.

| improve this answer | |
$\endgroup$
  • $\begingroup$ i'm using Prime95, wich is specifically designed for factoring mersenne primes $\endgroup$ – Omer Enes Nov 9 '19 at 21:35

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.