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 whatever size limit has been imposed on the other numbers in the table. This will be at least twice the limit used for non-Aurifeuillian numbers, and substantially more for some tables. In any examples below, the given table's size limit is assumed to be 1024 bits (i.e. exponents are limited so that all of the unfactored, non-Aurifeuillian numbers, as well as the unfactored L and M numbers in Aurifeuillian numbers, in the given table are less than 1024 bits in size).
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. But see the final paragraphs below for special considerations for some tables. 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, and the squarefree part of 12 is 3.
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.
For some tables, the algebraic portion of the Aurifeuillian numbers is larger than the L and M numbers. For example, the identity for the 5n+3n table is:
515h + 315h = ((55h + 35h) × (53h + 33h) / (5h + 3h)) × (54h + 8·53h3h + …) × (54h + 8·53h3h + …)
Here we see that the purely algebraic portion of the number accounts for 7/15 of the total size of the full number. However, since that portion is the product of factors which are 5/15 and 3/15 of the total, respectively, the largest individual factors in this algebraic portion will be at most 5/15 = 1/3 of the size of the full number. But this is still greater than the size of the L and M numbers, which are each 4/15 of the total. In such a situation, it is the size of the algebraic portion which must determine the table's maximum exponent for Aurifeuillian numbers, because otherwise there may be algebraic factors listed which don't actually appear in the table.
As a concrete example, for the 5n+3n table, if we extend the exponents for Aurifeuillian numbers so that the L and M numbers are all at most 1024 bits, then we could have a maximum exponent of 1635. However, 51635+31635 has 5545+3545 as an algebraic factor, and this number is larger than 1024 bits and therefore doesn't appear in the table, thereby causing problems for anyone trying to look up the factors of this number. The solution is to limit the exponents of Aurifeuillian numbers so that both the algebraic and the L and M portions of the number are less than the table limit. In this case, that means Aurifeuillian exponents should be limited to 1305, instead of 1635.
See the page on table limits for more on this, and for current values of the exponent limits for each table.