Factoring b^n – 1

Suppose you want to factor a number of the form bⁿ - 1.

There is a theorem that says that if m divides n then b^m - 1 divides bⁿ - 1.

Let's use this theorem to try to factor J = 2²⁰²³ - 1, a 609-digit number. Factoring such a large number would be more difficult if it didn't have a special form that we can exploit.

Our theorem tells us J is divisible by 2⁷ - 1 and 2²⁸⁹ - 1 because 2023 = 7*17*17.

Is J divisible by (2⁷ - 1)(2²⁸⁹ - 1)? In fact it is, but this doesn't necessarily follow from the theorem above because (b^m - 1) and (b^n/m -1) could share factors, though in this case they do not.

So we have

J = (2⁷ - 1) (2²⁸⁹ - 1) F

for some factor F. Now 2⁷ - 1 = 127, a prime. What about 2²⁸⁹ - 1?

By the theorem above we know that 2²⁸⁹ - 1 is divisible by 2¹⁷ - 1 = 131071, which turns out to be a prime. We can get a couple more factors of 2²⁸⁹ - 1 by consulting The Cunningham Project, a project that catalogs known factors of bⁿ 1 for small values of b. We learn from their site that 2²⁸⁹ - 1 is also divisible by 12761663 and 179058312604392742511009. All together

2²⁸⁹ - 1 = 131071 * 12761663 * 179058312604392742511009 * R

where

R = 3320934994356628805321733520790947608989420068445023

and R turns out to be prime.

So now we have five prime factors of J:

• 127
• 131071
• 12761663
• 179058312604392742511009
• R.

That leaves us with F above, a 520-digit number. It would seem we've gotten all the mileage we can out of our factoring trick. But there's something we haven't tried: We know that J is divisible by 2¹¹⁹ - 1 because 7 * 17 = 119 is a factor of 2023.

Now

2¹¹⁹ - 1 = 127 * 239 * 20231 * 131071 * 62983048367 * 131105292137

and so these prime factors divide J. However, two of these, 127 and 131071, we've already discovered. But we do learn 4 more prime factors. So

F = 239 * 20231 * 62983048367 * 131105292137 * G

where G is a 492-digit number. We can tell by Fermat's test that G is not prime, but I'm unaware of any clever technique for easily finding any of the factors of G.

***

In general factoring a 492-digit number is hard. There are RSA challenge numbers smaller than this that have not yet been factored, such as RSA-260, a 260-digit number. On the other hand, the RSA numbers are designed to be hard to factor. RSA-260 has two prime factors, presumably both the same order of magnitude. We get a little luckier with G. It has three relatively small factors that I was able to find:

G = 166684901665026193 * 3845059207282831441 * 153641005986537578671 * H

where H is a 436-digit number. I know from Fermat's test that H is composite but I could not find any factors.

Update: From the comments, 2605053667526976413491923719 is also a factor of G. I've updated the code below accordingly. Now the unfactored part H is a 408-digit number.

***

Here's Python code to verify the claims made above.

from sympy import isprimedef verify_factors(N, factors, full=True): prod = 1 for f in factors: assert(isprime(f)) prod *= f assert(N % prod == 0) if full: assert(N == prod)R = 3320934994356628805321733520790947608989420068445023factors = [131071, 12761663, 179058312604392742511009, R]verify_factors(2**289 - 1, factors)J = 2**2023 - 1prod = 127*(2**289 - 1)F = J // prodassert(J == prod*F)factors = [127, 239, 20231, 131071, 62983048367, 131105292137]verify_factors(2**119 - 1, factors)prod = 239*20231*62983048367*131105292137G = F // prodassert(F == G*prod)factors = [166684901665026193, 3845059207282831441, 153641005986537578671, 2605053667526976413491923719]verify_factors(G, factors, False)prod = 1for f in factors: prod *= fH = G // prodassert(G == H*prod)assert(not isprime(H))assert(len(str(J)) == 609)assert(len(str(F)) == 520)assert(len(str(G)) == 492)assert(len(str(H)) == 408)

Related post: Primality certificates

Update: See the next post for the case of bⁿ + 1.

The post Factoring b^n - 1 first appeared on John D. Cook.