A DISCUSSION OF INTEGER FACTORING FAMILIES

Part Seven: Basics of Integer Factoring

To wish a wish is to be fanciful, but eventually disappointing, and
To wish for more wishes is to be pragmatic, but infinitely disappointing.

Partial Table of Integer Factoring Families

Foreword

What is the purpose of Integer Factoring Families? This is a question no one actually asks, but I feel an obligation to answer none-the-less. In simplest terms, the purpose of Integer Factoring (in general) is to reduce the computational time required to determine the integer factors of (very) large integers. In this context, the purpose of Integer Factoring Families is to reveal mathematical relationships that facilitate computation shortcuts. Whether this is necessarily a good or a bad thing is an unresolved issue at this time, but I want to give anyone interested my honest appraisal.

Just a note to the readers who are interested in reading the spreadsheet images. I know that some of them are tiny in this format. Please use the Open Image in a New Tab function in your browser. In Firefox this is accessed by moving the cursor to the image and clicking the right mouse button. The image can be magnified by holding the Ctrl Key and the + Key down at the same time. If you already knew how to do this, give yourself a gold star.

This article is part of the series called the Basics of Integer Factoring. If you view my Lists and About data, all the other articles can be seen.

Chapter 1 — Background

Integer Factoring has been a mathematical study for a long time. Here is a current reference with some key concepts.

Wikipedia article for Integer Factorization (9 April 2023, at 16:45 UTC.)

In number theory, integer factorization is the decomposition, when possible, of a positive integer into a product of smaller integers.

When the numbers are sufficiently large, no efficient non-quantum integer factorization algorithm is known. However, it has not been proven that such an algorithm does not exist. The presumed difficulty of this problem is important for the algorithms used in cryptography such as RSA public-key encryption and the RSA digital signature.

Many cryptographic protocols are based on the difficulty of factoring large composite integers or a related problem — for example, the RSA problem. An algorithm that efficiently factors an arbitrary integer would render RSA-based public-key cryptography insecure.

Could Integer Factoring Families actually increase the speed of factorization enough to become a problem? I doubt it seriously for two reasons. First, it still performs functions through incremental iteration (which is inherently slow) and second, the probability of any individual being the first to stumble onto something that significant seems very improbable. This is true especially considering the amount of genius-hours that have been expended on this problem for literally centuries with no one coming forward with the magic algorithm. My money would actually be on the fact that this particular concept has been discovered and forgotten many times already, mainly because it is not the mythical all-solution.

Chapter 2 — Fermat’s Factorization

The primary engine of iterative integer factoring is Fermat’s Factorization Method.

Wikipedia article for Fermat’s Factorization Method (9 February 2023, at 05:09 UTC.)

Fermat’s factorization method, named after Pierre de Fermat, is based on the representation of an odd integer as the difference of two squares:

N = a² — b²

That difference is algebraically factorable as (a + b) (a − b); if neither factor equals one, it is a proper factorization of N.

Note that my preferred variable names used in this article replace “a” and “b” with “An” and “Bn.” See Appendix 1 — Standard Definitions and Equations for more variable definitions and related equations.

To use Fermat’s Factorization Method, the initial value of (An) is set to √N rounded up. The value of (Bn) is then calculated as the √[An² — N]. If (Bn) resolves as an integer, the solution is found, otherwise, (An) is incremented and the calculation is repeated. When a solution is found, the factors for N = Xn × Yn are simply Xn = (An — Bn) and Yn = (An + Bn). If (An — Bn) drops below 3, the procedure is stopped with no solution and the value of (N) is considered a prime number.

Although this procedure can be used to factor all odd numbers (and all even numbers divisible by 4,) our discussion will focus on factoring composite numbers with factors of 5 or greater. As such, it is recommended that a pre-check be performed to eliminate factors of 2 or 3 in case a prankster slips in a rogue value for examination (or perhaps even worse, the evaluator makes a data entry mistake.)

Our primary sample problem for the duration of this essay will be N = 19850791, which we conveniently know ahead of time to be 223 × 89017, (because we cheat.) Here is what factoring might look like in a typical spreadsheet.

Traditional Fermat Factoring for N = 19850791

If we use an unmodified Fermat’s Factorization Method we will indeed find the correct answer, but it requires 40165 iterations. (This chart has been truncated for clarity.) See Appendix 2 — Spreadsheet Labels and Highlights for my spreadsheet documentation notes.

Now, before someone who works with spreadsheets looks at this, I am going to take myself off the hook. This is a fictitious spreadsheet, i.e. a facade, that I am using to demonstrate this concept. It does not actually solve the factorization. I know the values I need to see and I direct the Skip To function to move down to where they are. Now at that point the spreadsheet will actually perform the math and show the solution, but the only way to use this when the solution is not known, is to use the Skip To repetitively until the solution is exposed. With a Skip To window of 10 lines, this will only require 4015 tries.

Chapter 3 — The Families

How then would Integer Factoring Families reduce the iterations required for Fermat’s Factorization Method?

A technical article describing how to create a Table of Integer Families along with notes related to Family Factoring methods is available at Introduction To Integer Factoring Families. This article will review much of that technical information, but my intention here is to provide a greater quantity of practical examples to show how all this actually works.

If we know the value of (An) then we can quickly calculate the values of (Xn) and (Yn). The nature of the problem, however, is that we do not know exactly which (An) will be the family home of the number (N) and that is why we must tediously hunt for the solution.

We start with the Family 44620, because from our factoring example above, we already know that An = 44620 when evaluating N = 19850791. Just a reminder, the family name is assigned to the value of (An) used to construct each data block. Thus the first three families are Family 0, Family 1, and Family 2. (See the illustration at the top of this article.) If we start at the family home, perhaps we can see clues that show us how to find the correct (An).

Family Factoring Data Block for An = 44620

Sadly, looking at this Family Factoring Data Block does not magically reduce any number of iterations from our routine. About all we see here are columns of numbers that have some odd symmetries. The Column[An] just repeats the family name on each line while the Column[Bn] is incremented by one on each line. The Column[N] shows all the (N) values that belong to this family. The next few columns, Column[N = An² — Bn²], Column[N = Xn × Yn], and Column[N = Expression] show the values that will combine to create each value of (N). Scanning down the Column[N] we see that the number we are seeking shows up towards the bottom of the truncated list and we find the result: 223 × 89017. The Column[An Parity] just reminds us that the family (An) is odd or even.

The Column[An Group] provides the family group of (An). It turns out that these series alternate between the families in a predictable pattern. Thus we learn that all family numbers (An) fall into three family groups. Discovery of the family group is done by taking the modulus of 3 of the value (An), An mod 3, which in all cases solves to Group 0, Group 1, and Group 2. (N) can only be factored if its Group number matches the An Group number, i.e. N Group = An Group.

The Column[N Series] provides the series of (N). The series is determined by taking the modulus of 6 of the value of (N), N mod 6. This number can be {0, 1, 2, 3, 4, 5}, but 0 and 4 duplicate 2 and the value of 1 actually indicates a number with the value of 7, e.g. 7 mod 6 = 1, thus our usable series set is {#2, #3, #5, #7≡#1}. I attach the “#” tag to variables or numbers to mark the series if highlighting clarifies a concept. Thus our original N#7 = 19850791#7 = 223#7× 89017#7. (If it annoys you, use an editor and replace all the “#” symbols with the phrase “Series”.) One final note on series: Series 7 is the result of multiplying same series and Series 5 is the result of crossing series, e.g. N#7 = X#7× Y#7, N#7 = X#5× Y#5, N#5 = X#5× Y#7, or N#5 = X#7× Y#5.

If we focus on the Column[N Series], we begin to see something interesting. We see many Series 2 and Series 3 values. These are numbers divisible by 2 and 3 respectively. We are not concerned about these, so we exclude all N#2 and N#3. We are thus left with two series that are relevant: Series 5 and Series 7. Note that numbers in Series 5 and Series 7 are generally not actually divisible by 5 or 7, it is just a classification system. There are two exceptions: 5#5 is divisible by 5 and 7#7 is division by 7. Note also that N#5 values do not show up in this family and in fact N#5 and N#7 never appear in the same family.

We know that the value N = 19850791 is Series 7, but which Group is it in?

Family Factoring Series and Groups

The illustration above shows all the relationships between Series and Groups. Thus the value N = 19850791#7 is either Group 1 or Group 2. This will be a frustration until someone figures out a way to differentiate between the two groups. In this case we know the Family An and therefore the Group Number is provided free of charge in the Column[An Group]. In the real world, you will not know this until the final factoring iteration is finished. (Not helpful!)

Column[N Drop] and Column[Drop Repeats] will be discussed in the next section.

By the way, we have a quick check of whether (An) will be even or odd. We know from prior work that the bottom value (N) of all Group 0 and Group 1 families is always N = An×2–1, so the last family is An = (N + 1)/2. Since this alternates between an odd number and an even number, we can deduce whether the proper family (An) is odd or even, e.g. if the last family (An:Last) is even then the family (An) required for the actual solution will also be even. Thus with no real effort, we eliminate 50% of all possible iterations and our sample problem now only requires 20083 iterations.

Traditional Fermat Factoring x2 for N = 19850791

In addition to changing the increments to 2, two other modifications to the Traditional Fermat Factoring are required to increment by 2. First, we check the value of (N + 1)/2 and determine whether it is even or odd. Second, if the initial An:1st value matches this state, An:2nd = An:1st, otherwise if it does not match this state, then An:2nd = An:1st + 1. Trial 1 will then use the value of An:2nd.

When we increment (An) we change the group number. The groups toggle between odd and even parity and they toggle between 0, 1, and 2. So, if we increment Group 0:Odd + 1 it becomes Group 1: Even. If we continue to increment we get Group 2:Odd, Group 0:Even, Group 1:Odd, Group 2:Even, and finally it becomes Group 0:Odd again. We will not get back to a Group 0 until we increment a total of 6 times.

Actually, being able to increment (An) by 2, means that we can now increment (An) by 6. If we increment Group 0:Odd + 2 it becomes Group 2: Odd and if we continue to increment we get Group 1:Odd. Yes, we are mixing groups and we should not do that. If (N) is a Series 7, then it can be either a Group 1 or Group 2. If we want to increment (An) by 6, this forces a dual iteration using both pathways when dealing with Series 7, whereas Series 5 will still only require a single pathway.

How do we find the correct initial value of (An) when working with a Series 7 value of (N)? Easy enough, start by setting An:2nd to the correct parity as above. If the An:3rd is not Group 1, simply increment it by 2 (so the parity is not changed) until it is a Group 1. Since this must be done for both group pathways, perform the same operation on An:4th until it is Group 2. It looks something like this.

Basic Fermat Factoring using Groups for N = 19850791

Incrementing the trials for dual pathways sounds tedious, but it is really simple. In the illustration above, the value for (An) for Trial 1, is the An:3rd:Group 1 and the value for (An) for Trial 2 is the An:4th:Group 2. During each trial after that, the values are each incremented by 6 forming two separate but entwined pathways. Our sample problem now only requires 13389 iterations. We have eliminated 33% of the remaining iterations and we now have reduced 67% of all possible iterations.

Knowing that Group 0 holds a single pathway for Series 5, we would expect even better results. Our sample problem for this test will be N = 20740961 = 233 × 89017. This number is very similar to the previous value we have been using, but with two valuable differences, it is Series 5 and Group 0.

We modify our procedure so that if the An:3rd is not Group 0, we increment it by 2 until it is a Group 0. Since this must be done for both group pathways, perform the same operation on An:4th until it is also Group 0. The value for (An) for Trial 1, is the An:3rd:Group 0, but since An:3rd = An:4th, the value for (An) for Trial 2 is the An:4th:Group 0 + 6 as it would be pointless to duplicate the iterations from the same starting value.

Basic Fermat Factoring using Groups for N = 20740961

This sample problem now only requires 6679 iterations. We have eliminated 67% of the remaining iterations and we now have reduced 83% of all possible iterations. Thus we begin to think, “Maybe this stuff can be useful!”

Chapter 4 — Using the Family Traits

We now know about Integer Families, Family Groups, and Integer Series. How else can we reduce the number of iterations using the families? First we need to examine the Family Traits.

Family Factoring Traits

This is an expansion of our Family Factoring Series and Groups Table from above, but with more confusing information added.

Why do we now have two series for Series 5 in Group 0? The two Series 5(A&B) are the result of multiplying across families. Sometimes the difference (or gap) between a Series 5 and a Series 7 will be 2 + 6Z, e.g. 5 × 7 where 7–5 = 2, and at other times it will be 4 + 6Z, e.g. 7 × 11 where 11–7 = 4. It seems trivial, but it does make a difference. (More on this later.) The difference between multiplication within Series 5 and within Series 7 is always 6Z, e.g. 5 × 11 where 11–5 = 6 or 7 × 13 where 13–7 = 6, so no differentiation is necessary.

What do all the other Family Traits do? We need to return to the Family Factoring Data Block shown above. On examination, certain data lines occur at regular intervals with a specific starting point. Specifically, we notice that starting with Bn = 3, we find a Series 7 every 6 lines. When all the Series 2 and Series 3 data lines are removed we are left with only those Series 7 data lines.

Condensed Family Factoring Data Block for An = 44620

When we determine the series of (N) and whether (An) is odd or even, we can look up the Family Traits for the Family Group. In our example, we have Series 7 and Group 1 with An:Even, so from the Column[An Even Bn Top] we find that the Bn:Top = 3. We use this Bn:Top to find the Family Reference Drop Point. Each family can use this drop point as a reference. All the Series 7 (and Series 5) data lines originate at this point and it is at the same location in all subsequent iterations of (An).

From the Column[An Even Drop Top] we find that the Drop:Top = 9, which is actually Bn:Top². The Family Reference Drop Point is calculated as An² — Drop:Top and is equal to 1990944391 in our example. The Column[N Drop] shows the difference between each candidate (N) in Column[N] and this Drop Point. If (N) were equal to 1990944391 with Drop = 0, we would have found a solution, 44617 × 44623, but since N = 19850791, we must move to down the column. The next N Drop = 72, which is also the value found in Column[An Even Interval]. This is the baseline drop for all values of (N) in this family and all subsequent families An:Group 1:Even. What that means is that the calculated drop using any (N) in this family will be similar in all related families and will always be divisible by 72, i.e. N Drop mod 72 will always be zero. The Column[Repeats] shows the N Drop divided by 72.

What do we get out of all this? If the N Drop Mod Family Interval = 0 (N Drop mod 72 = 0), then we can use the final Column[An Even Increment], which in this case is 36, to find the next (An). That means that instead of increments of 6, we can skip 36 values of (An). We will return to this thought later.

Chapter 5 — The Math Behind the Traits

Integer Factoring Families is not really providing any new information. All the Family Traits can be derived in other ways, much like ships used ropes and weights to determine water depth for centuries. Using that analogy, Integer Factoring Families offer the visual convenience of modern depth charts.

Let us start with the basic formula: N = An² — Bn². See Appendix 3 — Odd and Even Math for a refresher on the mating habits of odds and evens. With (N) being Odd, the only way to create an Odd value is to perform subtraction between an Odd and an Even number. Therefore An and Bn must be of opposite parity, i.e. one must be Odd and the other must be Even.

Using Series 7, Groups 1 and 2, we know the gap between the factors where N = Xn × Yn is 6Z = Yn — Xn, e.g. 6 × 2 = 12 = 17–5. From this we can derive some of the traits.

6Z = Yn – Xn
6Z = (An + Bn) – (An – Bn) = 2Bn
3Z = Bn =  √[An^2 – N] 
9Z^2 = Bn^2 = An^2 – N

Now we have the special case of Z = 0, which results in An² = N. Since N:Odd is a given, then √N:Odd is required as well, which means (An²) and (An) must be Odd! Consequently, Bn² and 9Z² must be Even. This also makes (Z²) and (Z) even as well, so Z = {0, 2, 4, 6, 8, … } and 9Z² = {0, 36, 144, 324, 576, … }. For Series 7, Groups 1 and 2, when An:Odd the value Bn:1st = 0 is the value of Column[An Odd Bn Top], the offset Bn:1st² = 0 is the value of Column[An Odd Drop Top], 36 is the value of Column[An Odd Interval], and the 9Z² series matches all the Drop Repeats.

What about Series 7, Groups 1 and 2, when An:Even? Well then, (Z) must be odd, so Z = {1, 3, 5, 7, 9, … } and 9Z² = {9, 81, 225, 441, 729, … }. Since Bn:1st = 3Z = 3 × 1= 3, we have an offset of Bn² = 9. So the corrected sequence is {0, 72, 216, 432, 720, … }. And again, for Series 7, Groups 1 and 2, when An:Even the value Bn:1st = 3 is the value of Column[An Even Bn Top], the offset Bn:1st² = 9 is the value of Column[An Even Drop Top], 72 is the value of Column[An Even Interval], and the 9Z² series matches all the Drop Repeats.

This process repeats for Series 5A, where the gap is 2 + 6Z = Yn — Xn, and Series 5B, where the gap is 4 + 6Z = Yn — Xn. For brevity, I have put the results in this chart. (Feel free to perform the derivations for yourself.)

Family Factoring Basis from Drop Analysis

Everything looks normal until we get to the Column[Mod ##]. For the Series 5 we quickly note that the basic Interval will not universally define the Drop Repeats. The only consistent results for Series 5A Drop Repeats is limited to Intervals = 24 and Series 5B is limited to 12. This is not to say that there are no big intervals available. It simply says that they are not found in this table.

Chapter 6 — Drop Synchronization

Now that we know that the increments of (An) can sometimes be greater than 6, we discover a new problem. When we try to do this with our current case, N = 19850791, we discover that we do not always get N Drop Mod 72 = 0. Our first attempt with An = 4456 and N Drop = 5136 yields the result 5136 Mod 72 = 24! Once again, we will need to synchronize (An) just as we had to do with increments of 2, and with two paths, we must do it for each pathway.

Synchronizing 19850791 with Top Drop

Using these new pathways, our next factoring attempt looks like this.

Basic Fermat Factoring using Families for N = 19850791

This sample problem now only requires 2231 iterations. We have eliminated 83% of the remaining iterations and we now have reduced 94% of all possible iterations. Before we celebrate though, we need a reality check.

Synchronizing 20740961 with Top Drop

This is the nightmare scenario, Group 0 and An:Odd. There is absolutely no gain over just using the basic iteration of 6. In fact, if I provided the illustration of this factoring it would be virtually identical to the illustration shown above for Basic Fermat Factoring using Groups for N = 20740961. (If you feel cheated, skip a few images ahead and I have provided the illustration in a different context.)

Chapter 7 — Transforms

Before someone thinks that cryptographic procedures should only use values of (N) that are Series 5, Group 0, where An:Odd, we need to discuss Family Transforms. There is a simple transform that can produce a notable effect. How would we do this?

We can cross the series and turn them into a different animals by multiplying by 5, but some thought is required. Knowing that N#5A = X#5 × Y#7 (or N#5B = X#7 × Y#5), what happens if we multiply by 5? We get 5 × N#5A = 5 × X#5 × Y#7. Knowing that 5 × X#5 = 5#5 × X#5 and that multiplying two Series 5 factors makes a Series 7 factor, we get 5 × N#5A = X:New#7 × Y#7 = N:New#7. Our N#5A:Group 0:Nightmare is now N#7:Group 1:Fast! Since by convention (X) is less than or equal to (Y), we must perform this transform on N#5B as well. Here we find that 5 × N#5B = 5 × X#7 × Y#5 = X:New#5 × Y#5 = N:New#7. Thus N#5B:Group 0 is now N#7:Group 2. The rule for multi-factor factoring is this: The order that factors separate from the factoring routine is dependent on how small the difference between (X) and (Y) is. Smaller gaps will appear before larger gaps do. That is why the (5×) appears to combine with the (X) term and not the (Y) term. If you go deeper in the factorization you will eventually find the 5 × Y factor.

Never multiply an N#7 by 5 as it will degrade to an N#5, i.e. N#5 = N#5 × N#7. In fact, there is no way that I can see to speed up a Series 7 using a transform.

When we multiply N = 20740961 by 5, it solves in 3880 iterations, but let us examine some more data points as this is a pretty radical idea.

Transforming Group 0 to Group 1 and 2

Seems to work fairly well. All we have to do is to remember to divide one of the factors by 5 to anti-transform it back. Note that the parity of (An) remains the same after the transform. (It always pleases me to no end when one of these crazy ideas pans out.) The final data entry, the one with the red highlight, points to a flaw in the logic. If 5 × X > Y then the transform will degrade the routine, e.g. N = 471773 = 673 × 701 with 5 × X = 3365 which is > Y = 701. By the same token, if 5 × X is near Y the routine will resolve quickly as seen with the N = 319235 and 314987. Will using this transform require a judgment call?

Not really. Exam any of the factoring illustrations above and note the values of √[An² — N]. These are approximate values of of (Bn) for each (An). Just periodically check the ratio: Yn/Xn = (An + Bn:Approx)/(An — Bn:Approx). When this value becomes greater than 5, the transform will be beneficial. It will look something like this.

Basic Fermat Factoring using Groups for N = 20740961 With Check for ×5

After Trial:260, check the data in the double red outline, we note that the transform is safe to use. The optimized solution would be to run two separate computers. On the first, the untransformed value runs seeking the golden ×5 trial. On the second, the transformed value runs. If the first computer exceeds the stop point without generating a solution, turn it off and let the second computer continue; otherwise, let them both run until a solution is generated or the stop point is reached.

If this concept were expanded, one would need to progressively multiply by {5, 5³, 5⁵, … } = {5, 125, 3125, … } until the number eventually becomes too large to manipulate. (Perhaps a problem for a 31st century super computer sitting idle in the nebula, or what ever the cloud is called by that time.)

All done? Not by a long shot! We still have the best part to examine.

Chapter 8 — Elimination for Cause

I am certain that there is a mathematical term for when the goal is not to find a relationship, i.e. Za is an element of Set Z, but instead to find the absence of all relationships, i.e. Set Z is not a subset of the Solution Set, but I do not know what that term might be, so I have “worded” it myself.

We generally understand that if we are looking for an elephant, that we must find a trunk somewhere, but if we have random pictures of an alleged elephant, much like a jigsaw puzzle, there may not be a trunk available to observe. That does not mean that we are at a dead end, however, because if we find a picture with zebra stripes, we know this is not an elephant. Thus if we can eliminate all animals except an elephant, all that is left is an elephant. That is the concept behind what I call EFC, Elimination for Cause.

How does EFC work?

First thing, we still have to synchronize our (N) with the Top Drop. This works just like before.

The next step is somewhat confusing (and a pain to implement,) but the concept is fairly simple. We are going to compare the ideal Drop Repeats with the actual Drop Repeats for (N) for each value of (An). We have already seen the ideal N Drops from Table of Integer Families and from the Tables of Drop Series and we know that the ideal N Drop Mod Interval = 0, so we simply divide the ideal N Drop with the Interval and create the ideal Drop Repeats series. We do the same for the actual N Drops from each of the (An) values that we will be iterating through and create the actual Drop Repeats series. Obviously, if they are the same, then we have found a solution, but there is a catch. (And it is maddening!) The Solution Set is an infinite set of all the prime numbers, so to make the sets match, we must compare every single prime in existence; however, all it takes is one failure to match and we eliminate an (An) value. Thus, it is not the values that match that tell us the right values of (An) to keep. It is the values that do not match that tell us the values to eliminate, i.e. we throw out the zebra stripes to find the elephant.

EFC Properties of Drop Reps for N=19850791

The first two sections of the spreadsheet show the actual math. The top section shows the Ideal Drop Solution and the bottom section shows the Actual Drop Solution. Both sections calculate the Drop Reps (Reps). The top section uses Bn² — Bn:Top² to calculate the Ideal N Drop and the bottom section uses the An² — Bn² — N to calculate the Actual N Drop. The Drop Reps (Reps) is the respective values divided by the Interval (Intrvl). The Keys are any prime numbers or combinations of prime numbers multiplied together, e.g. 6 = 2 × 3. The Mods below the Keys are N Drop Mod Key values and the list that they form is the Key Drop Profile. Comparing the top and bottom numbers we can easily see that some of the numbers generated for the Actual Values List do not show up in the Ideal Values List, e.g. at Key:7 = {2, 5}. These are the “zebra stripes” and allow us to eliminate these (An) values and mark them with a black “X”.

Since my spreadsheet does not eyeball very well, I have provided the instructions for matching the Actual and Ideal Values. This script works on LibreOffice Calc, so I can not guarantee results on the pay for abuse platforms.

Spreadsheet Details for EFC Key Lists for N=19850791

If I had provided longer tables of the Key Drop Profiles, it would have been more obvious that the profiles repeat themselves in the exact sequence in a block the length of the key they use. You can review the table above to verify this. In addition, the Master Key Profiles under the Column[Find] do this as well. Notice that the profiles have a double red outline to show the repeating blocks. This property allows us to perform a one time calculation of the profiles and use it on any new area of interest. Thus, if I had wanted to extend the Master Key Profiles to the two little subsections of the illustration, I could have done so, but to be honest, it was easier to just perform new calculations on the fly. If I were building blocks of a few thousand trials, I would have been more inclined to take advantage of the repetitions and apply the profiles sans performing any new calculations.

Returning to the statement that the Solution Set is an infinite set of all the prime numbers, here is what that looks like for a related number, N#7 = 314023, using keys up to prime number 59.

EFC Solution Set for N=314023

One can guess that the match data line continues to infinity. Whether that is true or not, it does have a very practical effect. We never know when some large obscure prime will take it off the rails. In this case we have a solution, so we know it is safe, but hypothetically, imagine running into something like 8683317618811886495518194401279999999 and having to start all over.

Chapter 9 — Strategies

The easiest strategy is to create a giant block using the Key Profiles and hold it side by side with the (An) progression and eliminate trials as they occur. I have used this method already and it provides a modest improvement in the factoring speed. See my other articles on the Basics of Integer Factoring for further information. I think this method could be improved by generating multiple blocks of intermediate size to use instead of the one monolith, but that is something for another day. Of course, please feel free to build the routine yourself.

The ultimate strategy would be to treat the problem as one would approach a combination lock. When all the combinations are in the right place the lock is open. I have looked at this for some time now and I just do not see a way to do this.

For today, I will exam a simple strategy that increases the size of the increments between each (An) value. It looks messy and complicated and I can hardly wait to get started.

Chapter 10 — Using the Anti-Keys

The EFC Keys allow us to eliminate various values of (An) as we iterate toward the solution, however, these keys can also be turned into Anti-Keys.

EFC Anti-Key: 3 for N=19850791

As an Anti-Key, an entire pathway can be removed. From the illustration above it can be seen that the An:4480 pathway, i.e. An = 4480 + 3 × 36 × Z = 4480 + 108 × Z = {4480, 4588, 4696, … }, will never generate a valid candidate. There is a downside though, An:4516 and An:4552 become the new pathways. Thus we trade one pathway for two, however, the upside is that our increment is tripled from 36 to 108! Note that since Fermat Factoring with Families requires two pathways to begin with, it will now require four pathways as this process is repeated for the associated An:Group 2. Here is what this looks like.

Fermat Factoring with EFC Anti-Key: 3 for N=19850791

This sample problem now only requires 1487 iterations. We have eliminated 33% of the remaining iterations and we now have reduced 96% of all possible iterations. How about the nightmare scenario?

Fermat Factoring with EFC Anti-Key: 3 for N=20740961×5

The first thing we notice is that I forgot to mention that we have to run Series 5 with the ×5 transform and therefore we need two initial pathways and thus four pathways total for this exercise, but the Anti-Key makes up for it. This sample problem now only requires 2584 iterations. We have eliminated 33% of the remaining iterations and we now have reduced 94% of all possible iterations. Note that after using the ×5 transform, the factor will become immune to Key:5. This is a consequence of N×5 Mod 5 = 0 causing An Mod 5 — Bn Mod 5 = 0, where An Mod 5 = Bn Mod 5. In fact, when any key column shows all “*”, then the key is most likely a factor of (N). There are some random exceptions, but the most notable exceptions are Key:2 and Key:3 and any composites containing them.

Trivia time:

• An:Group 0:Even will collapse a complete pathway with Key:2
• An:Group 1, An:Group 2, and An:Group 0:Odd are all immune to Key:2
• The An:Group 0 is completely immune to Key:3

If running a pure EFC without the ×5 transform and without any Anti-Keys, Key:2 and Key:3 should be conjoined into the Key:6, i.e. 6 = 2 × 3.

We can actually continue this game by creating an Anti-Key:5, an Anti-Key:7, an Anti-Key:11, and so on. With each prime we use, we gain iteration speeds: ×5, ×7, ×11, etc. We also increase the number of pathways to: 12, 48, 288, etc. See Appendix 4 — Spreadsheet Score Sheet for more information and some estimates of the effectiveness of various algorithms. Right now, I am stopping with the introduction to Anti-Keys using Key:3. I will try to get back to this later.

Chapter 11 — Using the EFC Keys

Ok, lets turn on the EFC function.

Fermat Factoring with EFC Keys: 11:13:17:19 and Anti-Key: 3 for N=19850791

Note that for the lines that have only a trial number and a value of (An), that no math is performed. These lines have been eliminated as seen by the “X” in the Column[Ok]. Probably not impressive to some folks, but for those of us that have tried to run a million square roots on numbers with 15 or more digits, it is a pretty big deal. The sample problem now only requires an estimated 137 iterations, or about 10 per 100 trials. We have eliminated 91% of the remaining iterations and we now have reduced 99% of all possible iterations.

Lets return to our troublesome An:Group 0:Odd sample value N = 20740961 = 233 × 89017.

Fermat Factoring with EFC Keys: 11:13:17:19 and Anti-Key: 3 for N=20740961×5

The sample problem now only requires an estimated 173 iterations, or about 10 per 150 trials. We have eliminated 93% of the remaining iterations and we now have reduced 99% of all possible iterations.

Chapter 12 — Final Notes

I originally thought that EFC was related to Integer Families, but after reading the factoring essay from Pere Montana Altes (08 Aug 2022), who was not using Integer Families, I realized that it is actually a property of Fermat Factoring. If you are a student of this discipline, I highly recommend you study this work.

I thought this would be a final summary of Integer Families and I could be done with it, but it appears there is still much work to do especially with the Anti-Keys. So all this is to be continued.

Whether this is necessarily a good or a bad thing is still an unresolved issue, but in my honest appraisal, it is worrisome. I continue to find hidden structure in places that I was not looking and these discoveries seem to always speed up the factorization process. I have passed the point where I have any faith in the myth that encryption with primes is impossible… er…difficult to break. I think it is only a matter of time before someone stumbles onto a very fast factoring routine, if not a direct solution.

Appendix 1 — Standard Definitions and Equations

• √[…] . . .— Square Root Function: Bn = √[An² − N]
• …^… . . — Raise … to the Power of …: Bn² = An² − N
• … : … . — Attributes: … is …: Z:Last:Even = Za:1st:Odd + Zb:1st:Odd
• An . . . — Fermat Factor of Base Value: An = (Yn + Xn)/2 where An ≥ √[N]
• Bn . . .— Fermat Factor of Separation Value: Bn = (Yn − Xn)/2 = √[An² − N]
• Gi . . .— Group Identifier: Gi = An mod 3 = {0, 1, 2}
• N’ . . .— Integer Prime Number: N’ = N’×1 ≠ N
• N . . .— Composite Integer & Factors: N = Xn×Yn ≠ N’
• N . . .— Fermat’s Factorization: N = An² − Bn² = (An − Bn)(An + Bn)
• Si . . .— Series Identifier: Si = N Mod 6 = {#2, #3, #5, #7≡#1}
• …#5 — Series 5: … is Series 5: N#5 = X#5× Y#7 -or- X#7× Y#5
• …#7 — Series 7: … is Series 7: N#7 = X#7× Y#7 -or- X#5× Y#5
• Xn . . — Smaller Integer Factor of N Xn = An − Bn where 1 < Xn ≤ Yn
• Yn . .— Larger Integer Factor of N Yn = An + Bn where Yn ≥ Xn > 1
• Z . . .— Temporary Variable Z = {Za, Zb, Zc, … }

Appendix 2 — Spreadsheet Labels and Highlights

Spreadsheet Labels and Highlights (that I generally follow)

Appendix 3 — Odd and Even Math

• Z:Even = Za:Odd + Zb:Odd; e.g. 12 = 7 + 5
• Z:Even = Za:Odd — Zb:Odd; e.g. 2 = 7–5
• Z:Odd = Za:Odd + Zb:Even; e.g. 7 = 5 + 2
• Z:Odd = Za:Odd — Zb:Even; e.g. 3 = 5–2
• Z: Odd = Za:Odd × Zb:Odd; e.g. 35 = 5 × 7
• Z: Odd = Za:Odd / Zb:Odd; e.g. 5 = 35 / 7 provided 35 mod 7 = 0
• Z:Even = Za:Even × Zb:Odd; e.g. 14 = 2 × 7
• Z:Even = Za:Even / Zb:Odd; e.g. 2 = 14 / 7 provided 14 mod 7 = 0
• Z: Odd = Za:Odd ^2; e.g. 25 = 5²
• Z:Even = Za:Even²; e.g. 36 = 6²
• Z: Odd = √[Za:Odd]; e.g. 5 = √[25] provided √[25]:Integer
• Z: Even = √[Za: Even]; e.g. 6 = √[36] provided √[36]:Integer

Reference Wikipedia Parity (mathematics) (29 March 2023, at 23:32 UTC.)

Appendix 4 — Spreadsheet Score Sheet

Spreadsheet Summary of Various Fermat Algorithms