1
$\begingroup$

I recently found a way to quickly find a factor of a given integer, starting from another integer not too far away from that factor and I was wondering whether this way is faster than trial division. It all depends on a simple lemma.

Lemma: Let $n,d\in\mathbb{N}$ with $d<n$, $d\mid n$ and let $k\in\mathbb{Z}_{\ge 0}$ with $$k<\frac{d^2}{n-d}.$$ Let $r$ be the least positive integer congruent to $-n$ modulo $d+k$. Now, either $\gcd(n,d+k)$, $\gcd(n,r)$ or $2$ is a non-trivial divisor of $n$.

Proof: We have: $$(d+k)\frac nd=n+\frac{nk}{d}\implies -n\equiv \frac{nk}{d}\pmod {d+k}$$ Also: \begin{align*} k &< \frac{d^2}{n-d}\\ nk-dk &< d^2\\ nk &< d^2+dk\\ \frac{nk}{d} &< d+k \end{align*} from which it follows that $r=\frac{nk}{d}$, so either $\gcd(r,n)$ is a non-trivial divisor of $n$ or $d\mid k$, in which case $\gcd(n,d+k)$ is a non-trivial divisor of $n$, except if $d=k=n/2$, in which case we have $2\mid n$. Q.E.D.

Now, In order to find a $d$, we just have to find $d+k$, so instead of finding one value ($d$), we need to find one of the $d^2/(n-d)$ values of $d+k$. We've nog longer got a single needle in a haystack, but a whole bunch of them. And we only need to find one.

Questions

  • First, did I make any mistakes?
  • If not, how long would it take to find a single non-trivial factor of a given $n$?
  • And how long would complete prime factorization take?
  • Is this faster than trial division (trivial if you've got the answer to the above questions)

Edit: From @mixedmath's answer, we know that we can ignore the time complexity of computing the $\gcd$ when calculating the time complexity of finding a single non-trivial factor. Let $$S(n):=\sum_{d\mid n, d\neq n}\left\lfloor\frac{d^2}{n-d}\right\rfloor$$ This is how many values of $d+k$ will give us a non-trivial divisor of $n$. When randomly guessing a value of $d+k$, the chance of succes is: $$\frac{S(n)}{n}$$ which means the chance of failure is $1-S(n)/n$. This means the time complexity should be: \begin{align*} &O(\log_{1-S(n)/n}0.5)\\ &= O\left(\frac{-\log 2}{\log(1-S(n)/n)}\right)\\ &= O\left(\left(\log\left(1-\frac{S(n)}{n}\right)\right)^{-1}\right) \end{align*}

$\endgroup$
6
  • $\begingroup$ Please describe your method a bit more (better give an algorithm), because it seems that you assume a factor $d$ of $n$. $\endgroup$ Aug 10 '17 at 10:29
  • $\begingroup$ @gammatester see my edit. $\endgroup$
    – Mastrem
    Aug 10 '17 at 11:06
  • $\begingroup$ @DavidK For all the numbers up until $10^4$, the average ratio between the number of non-trivial divisors and numbers of the form $d+k$ is $549.8$, which is a lot.I really think this can be faster than trial division, but it depends on the time complexity of computing the $\gcd$ $\endgroup$
    – Mastrem
    Aug 10 '17 at 12:25
  • $\begingroup$ You can use $\gcd(n,d)$ to determine if $d$ divides $n,$ so the time complexity of trial division no more than that of gcd--or to put it another way, gcd is at least as expensive as trial division. But if you can use one gcd as a substitute for a large number of trial divisions (as explained in mixedmath's answer) then that's a useful thing to do. $\endgroup$
    – David K
    Aug 10 '17 at 14:52
  • $\begingroup$ My earlier comment that "you have no good way to guess $r$" was wrong. I misread that step of the algorithm. Comment withdrawn. $\endgroup$
    – David K
    Aug 10 '17 at 15:16
5
$\begingroup$

Let's try your method on factoring $17\cdot 19 = 323$. There are two factors to identify.

Let's suppose that we were to identify the factor $d = 17$. What range of $k$ suffices? You say we need $$ 0 \leq k < \frac{d^2}{n-d} = \frac{17^2}{323 - 17} = \frac{289}{306} = 0.944...$$ This only leaves $k = 0$. So to guess $d$, one would need to guess exactly the factor $17$. This saves no time.

Perhaps the other factor is more helpful. Let's suppose we were to identify $d = 19$. Then $$ 0 \leq k < \frac{19^2}{323 - 19} = \frac{361}{304} = 1.1875.$$ So we would need to guess $d+k$ as either $19$ or $20$. This is not giving much space.

Of the three possible guesses for $d+k$, the only one that isn't a factor of $n$ directly (i.e. the only one that your method proposes that would be "another needle in the haystack") is $20$. Let's check that your method on $20$ works.

We compute $\gcd(n, d+k) = \gcd(323, 20) = 1$.

You say $r \equiv -n \pmod{d+k}$, and is chosen as the least positive residue. Here, that means $r = 17$, and $\gcd(n, r) = \gcd(323, 17) = 17$. So this identifies $17$ as a divisor.


The good news is that it does appear that your method does appear to work. The bad news is that in cases where $n$ is a product of two primes that are relatively near each other in size (the classic challenge), your method does not do very well and adds almost nothing to trial division. Even if the numbers are larger, you often gain nothing.

Your method works best when $n$ contains many factors. In particular, your method is best at finding the smallest nontrivial factor (corresponding to the largest nontrivial $d$, which has the largest $k$ range). When $n$ has many factors, you identify much more rapidly than random-guess trial division. Once you've identified the small factors, the method becomes worse and worse at identifying larger factors.


As a final note, you ask about the time complexity of computing gcds. Through the Euclidean algorithm, one can compute gcds in logarithmic time. You can pretend that this is instant, as gcds will not be what holds the computation back.

Computing gcds is so fast that many implementations of factorization algorithms first compute the gcd of $n$ with the product of the first very many primes, just to get all the small factors out of the way.

$\endgroup$
1
  • $\begingroup$ Actually, if $n=de$, guessing $d+k$ will be able to test $d/(e-1)$ factors at the same time. But since you are guessing on numbers of magnitute $d$, the speedup by a factor $\approx d/e$ still keeps the time required to get close enough to $d$ in order of $d/(d/e)=e$. This is what you get by trying divisibility by $3,5,7,\ldots$, or $\gcd$ with random numbers. $\endgroup$ Aug 10 '17 at 14:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.