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 isprime

def 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 = 3320934994356628805321733520790947608989420068445023
factors = [131071, 12761663, 179058312604392742511009, R]
verify_factors(2**289 - 1, factors)

J = 2**2023 - 1
prod = 127*(2**289 - 1)
F = J // prod
assert(J == prod*F)

factors = [127, 239, 20231, 131071, 62983048367, 131105292137]
verify_factors(2**119 - 1, factors)

prod = 239*20231*62983048367*131105292137
G = F // prod
assert(F == G*prod)

factors = [166684901665026193, 3845059207282831441, 153641005986537578671, 2605053667526976413491923719]
verify_factors(G, factors, False)

prod = 1
for f in factors:
    prod *= f
H = G // prod
assert(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.