Advice needed on what to do with a new elementary method of factoring integers.

Question

I literally stumbled on this really elementary (but promising) method of factoring integers. My maths knowledge being limited, I am not in a position to judge how efficient the method is with handling large numbers. I am wondering what my next steps should be. Should I post it here or just provide enough details so others can implement it and check it for themselves? (Sadly, I cannot code so I will not be able to do meaningful calculations myself).

Answer 1

Given a number $N=pq$ ( with $p>q$), this method is about building two numbers $N_1$ and $N_2$ whose sum adds up to $N$. There are of course many pairs $((N-1, N+1),...)$ but we consider only numbers that share a factor with $N$.

The closest number that share a factor with $N$ are $N_1$ = $(p-1) \cdot q = N - q$ and $N_2=(p+1) \cdot q = N + q$ but they are also the ones with the smallest gap since $N_2-N_1=2q$. These two numbers sandwich $N$ and share a factor with it. Notice that we have $N_1+N_2 = 2N$.

I am limiting myself to showing how the method works for number of the form $N=(6k+1)$ but the method can be expanded to other forms.

Now we express $N$ as $N = 36n + r$ and similarly $N_1 = 36i + s$ and $N_2 = 36j + t$. Because $N$ is the average of $N_1$ and $N_2$, we can see that the coefficients $(n,i,j)$ of $36$ and the remainders $(r,s,t)$ have similar average relations but not always as simple as $a + b = c/2$.

We obviously don't have $N_2-N_1$ or $N_1 \cdot N_2$ to use it with $N_2+N_1=2N$ to determine the factors so we have first to construct $N_1$ and $N_2$. It turns out that it is possible to build $N_1$ and $N_2$ from $N$ and from additional information that can be extracted from the behavior of numbers of the form $(6k+1)$. To begin with these numbers have only $3$ possible sum of digits: $1, 4,$ or $7$. This property is behind the patterns specific to these numbers and we will show how to exploit them to construct $N_1$ and $N_2$.

The numbers $N=(6k+1)$ can only have a remainder of $1,7,13,19,25,$ or $31$ when expressed as $N = 36n + r$. We need to find the patterns that are displayed by these numbers for a given sum of digits ($SD$). In the following we will restrict ourselves to the sum of digits $SD=7$. This sum of digits can be produced by multiplying numbers with these pairs of $SD$'s: $7 \times 1$, $4 \times 4$, $2 \times 8$, and $5 \times 5$. We are looking for patterns in $(r,s,t)$ and the coefficients. Basically we need to find out which $r$ is associated with the pair $(s,t)$.

It is easy to make a table for $SD=7$ and each of the four type of products $7 \times 1$, $4 \times 4$, $2 \times 8$, and $5 \times 5$. I will only give the values for the product $7 \times 1$ (because I don't know how to make tables). From numerical experiments (done by hand), we see that the remainders $(r,s,t)$ can only take certain values and then they cycle through. I use the word periodic. So if I did not miss one or more, they are $(r,s,t)=(25,18,32)$ and $(7,0,14)$. Unless I missed some, these are the only values the remainders $(r,s,t)$ will take when a number is a product of a $7 \times 1$ factors. But we have no way of knowing before factoring a number with $SD=7$ is it was a product of a $7 \times 1$ or some other product among the four possibilities. This means that we will be doing a lot more work to build the numbers $N_1$ and $N_2$ than we would if we could somehow tell the $SD$ of the original factors by looking at $N$ and maybe doing some tests (I could never figure out this problem).

So now we are ready to look at a really simple example to see how the method can be implemented.

We take $N = 7 \cdot 19 = 133 = 3 \cdot 36 + 25$. Because $r=25$, we know that the possible remainders are only those associated with $25$. There are few others than the ones listed above that come from products $4 \times 4$, $5 \times 5$ and $2 \times 8$. We know the answer so we will work backward. $N_1 = 7 \times 18 = 126 = 3 \times 36 + 18$ and $N_2 = 7 \times 20 = 140 = 3 \times 36 + 32$. So we can write $s + t = 2r$, and in terms of coefficients of $36$ we have $i + j = 2n$. The parity of $(n, i, j)$ plays a role in how we can write the average equations for the coefficients. In some cases, we need to borrow $1$ or $36$ to get the correct averages of both $(n,i,j)$ and $(s,t,r$).

The above case is pretty straightforward and we see that the averages can be calculated independently of each other, which is not always the case but it's pretty easy to know when the averages are dependent because we can only have integer values for these averages.

So we now have $i+j = 2 \times 3 = 6$ and $s + t = 2 \times n = 2 \times 25 = 50$.

Because the numbers$ N, N_1,$ and $N_2$ are the closest they can be while sharing a factor, we can reasonably assume that the coefficients will also be close to each other. So when we go from the sum $2n=6$ to individual values for $i,j$, it is also reasonable to start with the pair $(3,3)$. But we need to keep in mind that the pair $(2,4)$ should also be considered. An important question to which I don't have an answer is how many pairs should be considered before we give up. It is obvious in the above example that the pair $(0,6)$ and $(1,5)$ can be safely discarded because they would lead to numbers that cannot possibly share a factor with $N$. For $s + t = 50$, we can take the values $18$ and $32$ or $20$ and $30$ but certainly not $21$ and $29$ because $(21,29)$ is not a possible value.

So now we have the values of the remainders and the coefficients, we can build the numbers $N_1$ and $N_2$. One of the two is always divisible by $6$. It depends on the original factors form. If it is a $(6k+1)$, then $N_1 = (p-1) \cdot q = (6k+1-1) \cdot q=6k \cdot q$. If it is a $(6k-1)$ factor, $N_2$ will be divisible by $6$. A simple test to eliminate some values for $N_1$ and $N_2$. So we get $N_1 = 3 \cdot 36 + 18 = 126$ and $N_2 = 3 \cdot 36 + 32 = 140$. Taking the $\gcd(N,N_1)$ or $\gcd(N,N_2)$ will tell us they share a factor.

And like all factoring methods, this one can be used to test a number for primality. In this case, pairs of numbers can always be built but none will have a common factor if $N$ is prime.

One advantage of the method is that the difference or gap between the numerical values of the factors that limits the efficiency of other methods ( Fermat's...) plays no role here.

I would really appreciate any feedback.