The ultimate formula to factor them all.

Question

Context

I am working on Integer factorization problem, I found a formula for factoring numbers, and I need your help to simplify it. First I will explain how I get there and then I present the problem (This is actually an improvement of my previously posted idea).

Background

I want to find the factors of $d$ or in other words I want to know for what values of $x$ do you need to divide $d$ to get an integer solutions?

$$\frac{d}{x} = \left\lfloor\frac{d}{x}\right\rfloor$$

I found that in small ranges $\left\lfloor\frac{d}{x}\right\rfloor$ act as a linear line, and if you look on $x$ values higher then $\sqrt{d}$ you will see that the slope is equal to $1$. So in general you can write it like this:

$$\frac{d}{x} = \left\lfloor\frac{d}{\lfloor\sqrt{ d }\rfloor}\right\rfloor +y - 1*(x-\lfloor\sqrt{ d }\rfloor)$$

• $\left\lfloor\frac{d}{\lfloor\sqrt{ d }\rfloor}\right\rfloor$ is the starting point for $x=\lfloor\sqrt{ d }\rfloor$
• $1*(x-\lfloor\sqrt{ d }\rfloor)$ is the predicted change for the next $x-\lfloor\sqrt{ d }\rfloor$ values, assuming that it is a straight line
• $y$ is the error, as we don't really sure in what of those straight line $\frac{d}{x} = \left\lfloor\frac{d}{x}\right\rfloor$

So if I extract $x$ I will get the next thing:

$$x = \frac{a+b + y+ \sqrt{(a+b+y)^2 - 4d}}{2}$$

• $a = \left\lfloor\frac{d}{\lfloor\sqrt{ d }\rfloor}\right\rfloor$
• $b = \lfloor\sqrt{ d }\rfloor$
• $y$ positive integer

Question

When the next equation is an integer:

$$x = \frac{a+b + y+ \sqrt{(a+b+y)^2 - 4d}}{2}$$

• $a,b,d$ are positive known integers
• $y$ must be positive integer

Right now I am finding the solution by checking all the options. So it takes $546$ attempts to factor $652450640273$ to it's two dividers $787021$, $829013$

What can I do to reduce the number of options that I have for $y$?

Answer 1

Notice that, for any $k\in [\sqrt{d},d]$, there is a $y$ such that that choice of $y$ forces $x$ to equal $k$ - that is, our choice of $y$ completely determines our choice of $x$. Furthermore, given that it straightforwards to compute $y$ given $x$ and $x$ given $y$, it is clear that the problem of determining $y$ is, in terms of computation, equivalent to factoring $d$. There is a great deal of research into that subject, if you are really really intent on finding $y$.

The fact that your calculations don't reduce the problem of factoring isn't too surprising - you have come up with what is, roughly, the linear approximation of $\frac{d}x$ around $x=\sqrt{d}$ - so you can approximate the term $\frac{d}x$ with that. However, linear approximations are good at telling you "Well $\frac{d}x$ lies somewhere near this value on the number line" - but what you need to know is not the general area where $\frac{d}x$ lives (a sort of global property) but a local property: Is $\frac{d}x$ an integer? It is impossible to determine this with approximations - the error term completely determines the answer to that, so asking what the error term is is, in essence, rephrasing the original question.

Answer 2

As I mentioned to you in chat, you have essentially rediscovered Fermat's method for factoring $d$, by representing odd positive integer $d$ as the difference of two nonconsecutive squares.

That is, supposing we are able to express:

$$ d = X^2 - Y^2 $$

where $X,Y$ are positive integers that differ by more than one. Then:

$$ d = (X-Y)(X+Y) $$

and both factors are nontrivial (greater than one).

The best factoring methods known for large integers are essentially great-great-grandchildren of this idea, but they require some fairly sophisticated number theory and linear algebra for implementation.

You might be interested in a paper "Speeding Fermat's Factoring Method" by James McKee (1999), which the AMS has made available online. Generally speaking Fermat's method, if applied as an exhaustive search for factors of $n$, is $O(n^{1/2})$ complexity, the same as trial division. Where trial division is quick to find any small prime factors, Fermat's method is quick to find two factors of almost equal size. This probably accounts for the small number of steps you needed to find:

$$ 652450640273 = 829013\cdot 787021$$

McKee's approach is a heuristic method with estimated complexity $O(n^{1/4 + \varepsilon})$, so it is still exponential in terms of the number of bits of $n$. However it promises a significant improvement on trial division or Fermat's original method.

Another interesting improvement on Fermat's factoring method is described as "A One Line Factoring Algorithm" by William B. Hart (2012) which has "heuristic run time complexity of $O(n^{1/3})$ as a general factoring algorithm".

Answer 3

ST1 Factorisation by example, massively better than Fermat Factorisation. This overall method works for all numbers, but the example is 1 of a group of 8 within 36 possibles and is at a limit requiring only 2 pieces of logic and 1 guess. The other 28 require another term.

N = 3,911,290,831 (p x q)

3911290831/30 leaves remainder 1 therefore choices for B and C in (N-(BxC))/30 from (1 1) (7 13) (11 11) (19 19) (17 23) or (29 29)

(N - (BxC))/30

Let's try (11 11): (N - 121)/30 = (3911290831-121)/30 = 130376357(N2)

Sqrt((3911290831/900) = 2187(ignore remainder)

1300376357(N2) ends in 7. 2187 plus 2187+1 does not produce a number ending in 7, a requirement, therefore add 1. 2188 plus 2188+1 does produce a number ending in 7. Because using (11 11), (2188 + 2189 just the digits)/3 must leave remainder 1 , it doesn't. 2193 + 2194 ends in 7 and divided by 3 leaves remainder 1. Bingo!

(2193-n)30) +11 x (2194+n)30) +11 = 3,911,290,831 (p x q)

n = 684

p = 45311 q = 86321 45311 x 86321 = 3911290831 One number is almost twice the other. 1000 times better than Fermat? If I've written this wrong, sorry, it does work, l'm just losing the will!