# Factoring 2048 bit number is easy?

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..?

• Please learn to write in $\LaTeX$/MathJax. – kelalaka Oct 30 '19 at 17:38
• 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... – poncho Oct 30 '19 at 18:02
• Are you also Ömer Enes Özmen. If so, can merge your accounts. – kelalaka Oct 30 '19 at 19:12

## 1 Answer

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.

• i'm using Prime95, wich is specifically designed for factoring mersenne primes – Omer Enes Nov 9 '19 at 21:35