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.

I’ve written lately about two general ways to prove that a number is prime: Pratt certificates for moderately-large primes and elliptic curve certificates for very large primes.

If you can say more about the prime you wish to certify, there may be special forms of certificates that are more efficient. In particular, there are efficient tests to determine whether Fermat number or a Mersenne number is prime.

Pepin’s test, implemented in four lines of Python here, determines whether or not a Fermat number is prime. It can instantly prove that the known Fermat primes are indeed prime. It can quickly show that the next several Fermat numbers are composite, but the time required to run Pepin’s test increases rapidly for larger numbers.

The Lucas-Lehmer test, implemented in six lines of Python here, tests whether a Mersenne number is prime. The largest known primes are Mersenne primes because the Lucas-Lehmer test is relatively efficient, though it still takes a lot of effort to search for new Mersenne primes.

Certifying that a number is composite is potentially much easier than certifying that a number is prime. A famous example of a proof that a number is composite was Euler’s announcement in 1732 that

2³² + 1 = 641 × 6700417,

thereby proving that the fifth Fermat number is not prime, disproving Fermat’s conjecture.

Several Fermat numbers have been fully factored, concretely proving that they are composite, but some Fermat numbers have been proven composite via Pepin’s test that have not been factored. The analogous statement is true for Mersenne primes and the Lucas-Lehmer test.

I’ve written recently about a simple kind of primality certificates, Pratt certificates. These certificates are easy to understand, and easy to verify, but they’re expensive to produce. In order to produce a Pratt certificate that n is a prime you have to factor n-1, and that can take a long time if n is large [1]. So Pratt certificates are only used in practice for moderately large primes. “Moderate” could mean a 50-digit number, which is large for some purposes, but would not be considered large in the context of cryptography.

High-level description

Elliptic curve primality proofs are used to certify primes that are too large for Pratt certificates. The Goldwasser-Kilian theorem says that a number p is prime if there exists an elliptic curve with certain properties that depend on another prime q. As with Pratt certificates, this process is applied recursively: p is prime if q is prime, and q is prime if r is prime, … down some the base case of primes so small that they are recognized as prime.

The Goldwasser-Kilian theorem gives a lower bound on the size of q:

q > p^1/2 + p^1/4 + 1.

Ideally you find a q that’s not too much bigger than it needs to be. So to prove a 100-digit number is prime, maybe you reduce the problem to proving than an 80-digit number is prime, then reduce that to the problem of proving a 64-digit number is prime, etc.

Details

What is this elliptic curve in the theorem? You have to find a smooth curve mod p and a point M on the curve such that M is not the group identity, but qM is the group identity. How in the world would you go about finding such a curve? That’s a more complicated story, but the main idea of certificates is that they’re easy to verify, not easy to produce. Coming up with an elliptic curve primality proof is harder than verifying one [2].

Primality certificates need to be computationally easy to verify, not necessarily conceptually easy to verify. But they tend to be conceptually easier to verify than to produce as well. The rest of this post will outline how you could write your own code to verify an elliptic curve primality certificate.

How to verify from scratch

To verify an elliptic curve primality proof, you first [3] have to verify that someone has given you a smooth elliptic curve. They give you two numbers, a and b, and claim that

y² = x³ + ax + b

is a smooth elliptic curve over the integers mod p. To verify this you have to compute

4a³ + 27b²

and show that it is not divisible by n. Then you have to verify that the point M = (x, y) they gave you is on the curve, which requires sticking x and y into the cubic equation above and verifying that the equation holds mod p.

The last and most difficult step is to verify that qM gives the group identity for the elliptic curve. You have to add M to itself q times using the group law of the curve [4].

Implementing the group law for an elliptic curve modulo a prime is a little tedious, but the only difficult part is finding a multiplicative inverse mod p. Presumably your computing environment would have a library routine for modular inverses. For example, Mathematica has the function ModularInverse.

Related posts

• Cryptography articles
• How probable is a probable prime?

[1] If n is a safe prime then q = (p-1)/2 is also a prime, and so proving that q is prime is just about as hard as proving p is prime. Such hard luck can’t keep going. As you recurse you eventually get to primes p such that p-1 factors into pieces much smaller than p, but the process can start of being difficult.

[2] Elliptic curve primality certificates are sometimes called Atkin-Goldwasser-Kilian-Morain certificates or Atkin-Morain certificates because Atkin and Morain did a lot of work to make the idea of Goldwasser and Kilian practical.

[3] The Goldwasser-Kilian theorem also requires that p is not divisible by 2 or 3, but that’s trivial to verify.

[4] In practice you don’t literally add M to itself q times, but you produce a result that is the same as if you did. You’d use repeated doubling, analogous to using repeated squaring in fast exponentiation.

Suppose a number n written in binary has two 1s and all the rest of its bits are zeros. If n is prime, then the 1s must be the first and last bits of n. The first bit is 1 because the first bit of every positive integer is 1. The last bit is 1 because if the second 1 appeared anywhere else then n would be divisible by 2.

Here are the first four examples:

11_two = 3_ten
101_two = 5_ten
10001_two = 17_ten
100000001_two = 257_ten

Let’s count how many 0 bits each number contains. We get 0, 1, 3, and 7 if we count in base 10, or 0, 1, 11, and 111 if we count in binary. It seems that the number of 0 bits is either zero or a number whose binary representation is all 1s. In fact this turns out to be a theorem:

Suppose a number n is written in binary as a 1, followed by m 0’s, and finally a 1. Then if n is prime, then either m = 0 or the binary representation of m consists entirely of 1’s.

To prove this theorem, let’s move away from talking about bits and move toward more standard math terminology.

Our description of n in terms of bits is another way of saying

n = 2^k + 1.

And our description of m is another way of saying

m = 2^j – 1.

And a 1 followed by m 0’s and then a 1 is a number of the form

2^m+1 + 1.

So the theorem above is saying that if 2^k + 1 is a prime number, then k is a power of 2.

Here’s a proof. Suppose k is not a power of 2. Then k has an odd factor, i.e. k = ab where b > 1 is an odd number. In that case we can factor 2^k + 1 as follows:

We’ve shown above that 2^k + 1 is prime when k = 2^j and j = 0, 1, 2, and 3.

What about j = 4? Yes, 2¹⁶ + 1 = 65537 is prime.

We’re on a roll. What about j = 5? Is 2³² + 1 prime? No, it’s not.

What about larger values of j? Do any of them produce primes? Nobody knows.

This post has secretly been about Fermat primes. The nth Fermat number is given by

Fermat observed that F_n was prime for n = 0, 1, 2, 3, and 4. He conjectured that F_n is prime for all n, but Euler factored F₅, disproving Fermat’s conjecture.

Why did this post delay using standard terminology? The first reason was to unpack the math. The direct discussion can go by so quickly that it’s hard to appreciate what it is going on. The second reason was to illustrate how much easier things can become when we switch from discussing bit patterns to using math notation. Sometimes things go the other way, with bits being easier to understand than mathematical equations.

Last week I wrote about primailty certificates. These certificates offer a way to verify that a number is prime using less computation than was used to discover than the number was prime.

This post gives a couple more examples of primality certificates using sonnet primes. As described here,

These are primes of the form ababcdcdefefgg, the rhyme scheme of an English (Shakespearean) sonnet, where the letters a through g represent digits and a is not zero.

There are 16,942 sonnet primes, ranging from 10102323454577 to 98987676505033.

Here are Pratt certificates verifying that the largest and smallest sonnet primes are indeed primes.

As before, I assume primes less than 100 are recognizable as primes, though the certificate algorithm continue until all branches of the tree end in a 2.

The quadratic reciprocity theorem addresses the question of whether a number is a square modulo a prime. For an odd prime p, the Legendre symbol

is defined to be 0 if a is a multiple of p, 1 if a is a (non-zero) square mod p, and -1 otherwise. It looks like a fraction, but it’s not. It acts something like a fraction, which was presumably the motivation for the notation.

The quadratic reciprocity theorem says that if p and q are odd primes, then

We can rewrite this in the less symmetric but more useful form

The idea behind quadratic reciprocity as an algorithm is that when p < q, we can use the equation above to turn a question about the existence of square roots mod q into a question about the existence of square roots mod p. This is progress because p is smaller, and we get to reduce q modulo p.

The quadratic reciprocity theorem only applies to the case of odd primes. So we need a couple more facts to complete our algorithm: how to deal with numbers that are not odd or not prime.

If the “numerator” of our Legendre symbol is not prime, we factor it using the theorem that

for numbers m and n that are not multiples of p. And if we get a factor of 2 in a numerator there is a theorem that says

result

Is today a square for Jenny?

As an example, we will determine whether 112023, today’s date, is a square mod 8675309, the telephone number in the 1981 pop song 867-5309/Jenny.

We begin by factoring 112023. A consequence of the factoring rule above is that we can throw away prime factors with an even exponent, and we can replace odd exponents with 1. Therefore

The full calculation is worked out in detail here. We apply the factoring rule and quadratic reciprocity over and over until we get Legendre symbols with such small numbers that we can evaluate them directly. In our case, all we need to know is that 1 is a square mod 3 and 2 is not.

The bottom line of our calculation is 1, so yes, 112023 is a square mod 8675309.

Calculating modular square roots

The quadratic reciprocity theorem gives us a way to determine whether a number has a square root mod p but it does not give us a way to calculate that root. Or rather those roots. Always two there are, like siths.

We could calculate the square roots of 112023 mod 8675309 using the Tonelli-Shanks algorithm, which is unfortunately more complicated than the quadratic reciprocity algorithm.

Mathematica can give us the roots, presumably by using some variation of the Tonelli-Shanks algorithm, or perhaps a newer algorithm. In any case,

    Reduce[x^2 == 112023, x, Modulus->8675309]

tells us the roots are 1955529 and 6719780. The latter is the negative of the former, modulo 8675309, i.e. -1955529 = 6719780 mod 8675309.

You can verify that the roots are correct by computing

1955529*1955529 – 440802*8675309 = 112023

and

6719780*6719780 – 5205053*8675309 = 112023.

Almost all binomial coefficients are divisible by their row number.

This is a theorem from [1]. What does it mean?

If you iterate through Pascal’s triangle, left-to-right and top-to-bottom, noting which entries C(m, k) are divisible by m, the proportion approaches 1 in the limit.

The author proves that the ratio converges to 1, but doesn’t say anything about the rate at which it approaches 1. By writing a little Python script we can observe how the ratio approaches 1.

First, let’s create a generator that will let us walk through Pascal’s triangle.

    def pascal():
        m, k = 0, 0
        while True:
            yield (m, k)
            k += 1
            if k > m:
                m += 1
                k = 0

We can use this generator to illustrate Pascal’s triangle mod row number.

    from math import comb

    p = pascal()
    m, k = next(p)
    while m < 10:
        ch = "*"
        if m > 0 and comb(m, k) % m == 0:
            ch = "0"
        print(ch, end="")
        if m == k:
            print()
        m, k = next(p)

This produces the following.

    *
    00
    *0*
    *00*
    *0*0*
    *0000*
    *0***0*
    *000000*
    *0*0*0*0*
    *00*00*00*

The theorem says that as we keep going, the proportion of 0’s in a diagram like the one above approaches 1.

Now let’s plot the proportion of zeros as we traverse Pascal’s triangle mod row number.

    N = 1000
    x = np.zeros(N)
    p = pascal()
    for n in range(N):
        m, k = next(p)
        if m > 0 and comb(m, k) % m == 0:
            x[n] = 1
    y = np.arange(N)
    plt.plot(y, x.cumsum()/y)
    plt.show()

Here’s what we get.

The ratio doesn’t seem to be converging to 1. If I had to guess, I might say it’s converging to 0.7 by looking at this plot. But if we go further out and switch to a log scale it seems more plausible that the sequence is converging to 1, albeit very slowly.

[1] Heiko Harborth. Divisibility of Binomial Coefficients by Their Row Number. The American Mathematical Monthly, Jan. 1977, Vol. 84, No. 1, pp. 35–37.