What is the most efficient algorithm for factorisation when an approximate value of one factor is known

If I am given the following number:

1522605027922533360535618378132637429718068114961380688657908494580122963258952897654000350
692006139

And am told that one of the factors is in the range:

38035634573286525913223768327418691775212180785884 -
37933217936943673922808872755445625858565536638189

What would be the most efficient (classical) algorithm for calculating the factors? Obviously, brute forcing would be out of question, and the Quadratic and General Number Field Sieves wouldn't be able to use the range.

Solution 1:

We know that $N$ has a factor $p$ between $0.97213\sqrt N$ and $0.97476\sqrt N$. Then for suitable $a$ (small, but with good factors), $N'=aN$ may have a factor very close to $\sqrt{N'}$, and that can be found by Fermat's method. For example if $a=20\cdot 19$ and $p\approx 0.97476\sqrt N$ then $20p\approx 1.00008\sqrt{aN}$. This $a$ was just a simple ad hoc example and already seems somewhat helpful (for a part of the possible factor range). To me it sounds promising to go look for a nice $a$ with many factor between $0.97213\sqrt a$ and $0.97476\sqrt a$.

Solution 2:

Your range has an upper bound about 2-3 percent larger than the lower bound. So, the answer is that there is nothing much you can do simply based on a range like that. This is because you could start with a small range, say 100-102. Then 102-102*1.02, then 102*1.02-102*1.02^2, and so forth. Proceeding like that, you only need about log base 1.02 of $n$ steps to cover the whole range of factors (well, half that to get to the square root). Thus, if you had a good algorithm using ranges of that fineness, you would have a good algorithm in general.

Just multiply the complexity of your special case algorithm by a linear factor, and you have the complexity of a valid general factoring algorithm. Since a linear factor is small beans in the world of integer factorization, an interval that is only fine to the tune of a few percent is therefore essentially useless in simplifying the problem.

Now, your range is very close to the square root, so maybe you are thinking something can be done from that. This still doesn't help, because you could proceed as I mentioned before, but at each step multiply the range or number to factor by an integer so as to transform the problem into one where the range covers any particular value calculated based on the number to factor (like its square root). Then an algorithm that could use a range with a fineness on the order of a couple percent, located anywhere specific with respect to the number to factor, can be used to construct a general purpose algorithm at the cost of a linear factor.

So, the answer to your question is definitely no, a huge range like that is not helpful. You'd just have to forget about the range and use a general purpose algorithm.

Solution 3:

The question, in its full generality, does not really have an answer, in my opinion. Consider the problem formulated as follows:

find a computationally efficient algorithm to factorize $N$ knowing that it has a divisor in the range $[a,b] = \{a, a+1, \dots, b-1, b\}$

and call it "problem $P(N,a,b)$". As you are going to see, a good answer can be given only if further information about the size of $b-a$ is given.

If $b-a$ is $O(\log^k N)$, then brute force is polynomially-fast, therefore "very" fast (in the sense of computational complexity) and, if $k$ is small, it is also fast in practice on current hardware.

On the other hand, the very special instance $P(N,1,N)$ is precisely the problem of integer factorization - which shows that in general $P(N,a,b)$ is equivalent to the problem of integer factorization, for which many algorithms exist, none of them fast (in the sense of computational complexity).