Aurifeuillian Factorizations

A Note on Aurifeuillian Factorizations

For each pair of numbers (a, b), a subset of the numbers an ± bn have algebraic factors based on algebraic identities involving some special polynomials, known as "Aurifeuillian" polynomials (from the mathematician L.F.A. Aurifeuille). The details of generating these polynomials and the corresponding factors are complex (see Brent, On computing factors of cyclotomic polynomials), but for our purposes here, the following will serve to explain the presence of these entries in the Homogeneous Cunningham tables.

When a number has an Aurifeuillian factorization, it splits into two roughly equal sized numbers. By convention, these are referred to as the associated L and M numbers. These numbers may have their own algebraic factors, and often the original number will have other algebraic factors as well. So an Aurifeuillian factorization allows one to factor a number significantly larger than one without such a factorization for the same cost. For this reason, the tables extend the exponent limits for numbers with Aurifeuillian factorizations. Specifically, the exponents go up to a value which keeps the L and M numbers under 1024 bits. This will be at least twice the limit used for non-Aurifeuillian numbers, and almost four times the limit for some tables.

As a simple example, consider the table for 4n+3n. Assuming h is odd, with h = 2k - 1, the algebraic identity of use here is:

43h + 33h = (4h + 3h) × (4h - 2h3k + 3h) × (4h + 2h3k + 3h)

For any given h, the three factors on the right side of this identity will all be approximately the same size. The first one is an algebraic factor, and it will already have an entry earlier in the table. The second two are the L and M numbers, respectively. Each of them will be approximately one-third the size of the full number on the left. So for the 4n+3n table, the exponents for numbers with an Aurifeuillian factorization are allowed to be three times as high (1533) as for the other numbers in the table (511) and still be assured that all numbers are less than 1024 bits in length. The relevant identity for other tables may be much more complex than this one, and the algebraic part may not always be one-third of the total size. But the L and M factors will always be about the same size as each other, so each is at most half of the total size, meaning that the tables will always be extended to at least twice the exponent limit for Aurifeuillian factors as for other numbers (see e.g. the 5n+3n table for a much larger extension). The full list of algebraic identities used in each table is shown here.

For a given a and b, the Aurifeuillian polynomials and algebraic characteristics are determined by the squarefree part of the product a × b. Here "squarefree part" means the number which remains when all squares are divided out of the original number, leaving a number that is just a product of distinct primes, all with a power of 1. So for example, the squarefree part of 24 is 6.

If we let r be the squarefree part of a × b, then we have the following:

So, for example, with a = 8 and b = 3, we get r = 6, so we expect to see Aurifeuillian factorizations in the table for 8n+3n, and those factorizations should appear whenever n is an odd multiple of 6. And indeed, that table shows entries for 6L, 6M, 18L, 18M, 30L, 30M, etc.

By contrast, with a = 12 and b = 7, we get r = 21, so we expect to see these factorizations on the minus side, i.e. in the 12n-7n table, and they should appear whenever n is an odd multiple of 21. Sure enough, there are entries for 21L, 21M, 63L, 63M, etc. in that table.

Exceptions occur when one of the Aurifeuillian factors happens to be 1. In such a case, the tables treat the number in an ordinary (i.e. non-Aurifeuillian) way. This occurs for 36+26 and 43+33 (see the example above of the identity used in the 4n+3n case, set h = 1, and note that the L factor on the right will turn out to be 1).

The determination of algebraic factors of individual L and M numbers is involved (details can be found in the Cunningham Book, 3rd edition, section III.C.2), but the following will demonstrate all of the algebraic considerations for an example number.

Consider 7105+4105. With a = 7 and b = 4, we get r = 7, so this number has an Aurifeuillian factorization. For h odd, with h = 2k - 1, the relevant identity is:

77h + 47h = (7h + 4h) × (73h + 3·72h4h + 3·7h42h + 43h - 2h7k(72h + 7h4h + 42h)) × (73h + 3·72h4h + 3·7h42h + 43h + 2h7k(72h + 7h4h + 42h))

As with the earlier example above, there are three factors on the right, the first of which is algebraic and is accounted for earlier in the table, and the next two of which are the L and M factors, respectively. Note that here the L and M factors will each be approximately 3/7 of the size of the full number, so the exponent limit for Aurifeuillian factorizations (847) in the 7n+4n table can be approximately 7/3 that of regular numbers (364).

Setting h to 15, we get that 715 + 415 is an algebraic factor. That number has its own algebraic factors, found in the straightforward manner for non-Aurifeuillian numbers, so it is comprised of all factors in the table on the lines for 1, 3, 5, and 15. Additionally, the L and M numbers each have their own algebraic factors. Specifically, 105L has 7M, 21M, and 35L as factors, while 105M has 7L, 21L and 35M as factors. As with normal numbers, algebraic factors are all omitted from each line in the table. So if one wished for a list of all factors of 7105 + 4105, one would need to gather all factors shown in the table on the lines for 1, 3, 5, 7L, 7M, 15, 21L, 21M, 35L, 35M, 105L, and 105M.