An old multiplication technique and its reverse for Integer Factoring

An ancient Indian multiplication technique is as follows:

$$\array{ a=107 & +7 & (\text{base}\space r=100)\\ b=113 & +13 \\ \hline (a+b-r)=(107 + 13) & (7 \times 13) & \space\text{or}\\ (b+a-r)=(113 + 7) & (7 \times 13) \\ \hline 120 & 91 \\ \hline 120 \times r + 91 = 12,091 & = 107 \times 113 }$$

Let $a,b \in Z$ and we want to compute the product $z = ab$.

We write $a, b$ in the first column one below the other. We choose a base $r > 0$, in this case $100$ and write the excess or deficiency of $a,b$ with respect to $r$ in the second column. In this case, the excess over $r=100$ for $107$ is $+7$ and for $113$ is $+13$. We then compute the diagonal sum, it doesn't matter which diagonal as both will sum to the same number. In this case it is $107+13 = 113+7 = 120$. We then compute the product of the excess (or deficiency), in this case $7 \times 13 = 91$. The required product is

$$z = (a+b-r)r + (a-r)(b-r) = 120*100 + 91 = 12091$$

As we can see, a convenient choice of the base $r$ helps us write the product easily in terms of the diagonal sum and the product of the excess (or deficiency).

If we look at the reverse problem of factoring $12091$, we could again choose the base $r = 100$. It then gives us

$$12091 = 91 \mod 100 + \bigg\lfloor {12091 \over 100} \bigg\rfloor \times 100 = 91 + 120 \times 100$$

Factoring the smaller number $91$ into $7 \times 13$ helps us determine the factors of $12091$ as $r + 7 = 107$ and $r + 13 = 113$.

This works only because the base $r$ is special where $(a-r)(b-r) < r$. It will work for other $r$, but we will have to deal with the carry i.e., $\bigg\lfloor {(a-r)(b-r) \over r} \bigg\rfloor$

Question:

1. The case of $0 \le (a-r)(b-r) \lt r$

Let $\bigg\lfloor {z \over r} \bigg\rfloor = a + b - r$.

• Given $z$ could we determine an $r$ such that $(a-r)(b-r) < r$ without any additional knowledge of anything about $a, b$ and with $(a-r)(b-r) \ge 0$?
• Is such an $r$ guaranteed to exist?
• Note that if $(a-r)(b-r) = 0$ then $r$ is a divisor of $z$

2. The case of $(a-r)(b-r) \ge r$

Let $\bigg\lfloor {z \over r} \bigg\rfloor = a + b - r + k$ for some integer $k = \bigg\lfloor {(a-r)(b-r) \over r} \bigg\rfloor$.

$$(a-r)(b-r) = kr + (z \mod r)$$

• If case (1) is not possible for a given $z$ (i.e, $r$ satisfying the criteria does not exist), could we find an $r, k$ that satisfies case (2)?
• As an aside, the equality condition $(a-r)(b-r) = r$ gives us $r$ as a trivial divisor of $z$.

If we are able to choose such an $r$ (or $r, k$ for case (2)) depending on $z$ alone, we will have a fast factoring algorithm.

Update (Oct 21, 2020):

There is an interesting empirical observation from the plot of $\lfloor {z \over r} \rfloor + r$ and its relationship to the sum $a+b, z = ab$ with $a,b$ positive. Plot shown below for $z=12091, a+b=220$.

Here is a closeup of the range where the curve hits minimum.

This means, if we pick a reasonably good estimate for $\lfloor {z \over r} \rfloor + r$ with $r = r_e$ being the corresponding value of $r$ and also pick random $r_0$ and $r_1$ such that $r_0 < r_e < r_1$, we can then determine the minimum $\lfloor {z \over r} \rfloor + r$ using successive bisection of the range $[r_0, r_1]$ since the minimum value of $\lfloor {z \over r} \rfloor + r$ must lie in either $r \in [r_0, r_{mid}]$ or $r \in [r_{mid}, r_1]$ where $r_{mid} = {r_0 + r_1 \over 2}$.

The initial estimate for $r_e$ could be:

$$r_e = {{2 + \lfloor {z \over 2} \rfloor} \over 2}$$

With successive iterations, we narrow the range until we are left with a range of width 1 $(r_1 - r_0 = 1)$ and one of the range bounds must result in the minimum for $\lfloor {z \over r} \rfloor + r$. This would require $O(\log(z))$ steps.

Conjecture C1: The conjecture is that the actual value of $a+b$ lies within a bounded distance from the minimum of $\lfloor {z \over r} \rfloor + r$ for composite $z$.

I am not sure if this conjecture is true. It would be very interesting if this conjecture is indeed true and the bounded distance is small relative to complexity of other factoring algorithms.

For $z$ prime, we get a plot as given below (example for $z = 4397$, prime):

As we can observe, for prime $z$, the distance between the sum of divisors (i.e, $a+b = 1+z$ is maximal from the minimum of $\lfloor {z \over r} \rfloor + r$.

For $z = 3 \times \ 443 \times 617 = 819993$, the plot of $\lfloor {z \over r} \rfloor + r$ is given below:

Here's the closeup of the plot of $\lfloor {z \over r} \rfloor + r$ for $z = 3 \times \ 443 \times 617 = 819993$

If $z$ is composite, there should be a minimal sum of divisors $a+b$ among all possible combination of divisors $a,b$ and if the conjecture is true, is the minimal $a+b$ at a bounded distance from the minimum of $\lfloor {z \over r} \rfloor + r$ that gives us an effective search procedure for $a+b$?

Additional conjectures and comments:

Conjecture C2: The minimal sum of divisors $a+b \ge \min(\lfloor {z \over r} \rfloor + r)$

Observation O1: Since $z$ is assumed to be odd, the divisors $a,b$ are both odd. Therefore, the sum of divisors $a+b$ is even. Assuming Goldbach's conjecture to be true, we should be able to partition $a+b = 2u = P+Q$ with $P,Q$ prime.

Conjecture C3: The value of $z \mod r$ for $r$ such that $\lfloor {z \over r} \rfloor + r)$ is minimum yields a non-trivial divisor of $z$ in $GCD(z \mod r, z)$.

Empirical data for Conjecture C3 in update section (dated Oct 23, 2020) below. [Update: Oct 23, 2020 - $\color{red}{\text {The Conjecture C3 is false.}}$]

Counterexample is $z = 991 \times 443 = 439013$. Minimum value of $\lfloor {z \over r} \rfloor + r)$ is $1325$ and $r \in [640, 686]$ and none of the $z mod r$ have a $GCD(z mod r, z) \ne 1$. Therefore, Conjecture C3 is false.

Update: Oct 22, 2020

Theorem: Conjecture C2 is true

Proof: Conjecture C2 states that The minimal sum of divisors $a+b \ge \min(\lfloor {z \over r} \rfloor + r)$.

Let $⌊z/r_m ⌋+r_m=\min(⌊z/r⌋+r)$ be the minimum value. $$z=⌊z/r_m ⌋ r_m+(z \mod r_m)$$ Also, let $(z/a).a+0$ be the divisor decomposition of $z$. Here $a=r$ and $b=z/r=⌊z/r⌋$. This also holds if we swap $b=r,a=⌊z/r⌋$. This gives the equality $$a+b=⌊z/r⌋+r$$ If we choose an $r=r_m$, such that $r_m≠a$ and $r_m≠z/a$, we have $$⌊z/r_m ⌋=(a+b-r+k)=(a+b-r_m+k)$$ where,

$k$ is the carry $⌊(a-r_m )(b-r_m )/r_m ⌋$ and

$z \mod r_m$ is the remainder $(a-r_m )(b-r_m ) \mod r_m$

Therefore, $$a+b=⌊z/r_m ⌋+r_m+k$$ $$a+b=⌊z/r_m ⌋+r_m+⌊(a-r_m )(b-r_m )/r_m ⌋$$ $$a+b>⌊z/r_m ⌋+r_m$$

So, we have shown that $a+b≥⌊z/r⌋+r$ for any $r$.

Since, $\min(⌊z/r⌋+r)$ is the minimum value of $⌊z/r⌋+r$, we have $$a+b≥ \min(⌊z/r⌋+r)$$

Hence the proof.

Update: Oct 23, 2020

Conjecture C3: The value of $z \mod r$ for $r$ such that $\lfloor {z \over r} \rfloor + r$ is minimum yields a non-trivial divisor of $z$ in $GCD(z \mod r, z)$.

[Update: Oct 23, 2020 - $\color{red}{\text {The Conjecture C3 is false.}}$. See counterexample above. $z = 439013 = 991 \times 443$. Leaving past update as is for posterity.]

Here is some empirical data for this conjecture:

This table is for $z=12091=103\times117$. The minimum of $\lfloor {z \over r} \rfloor + r$ is $219$. The values of $r$ that give this minimum value for $\lfloor {z \over r} \rfloor + r)$ are $r \in [108,112]$. For $r = 112$, we have $z \mod r = 107$ and $GCD(107, 12091) = 107$, a non-trivial divisor of $z$.

This table is for $z=13733=31\times443$. The minimum of $\lfloor {z \over r} \rfloor + r$ is $234$. The values of $r$ that give this minimum value for $\lfloor {z \over r} \rfloor + r)$ are $r \in [109,126]$. For $r \in \{110,124\}$, we have $z \mod r = 93$ and $GCD(93, 13733) = 31$, a non-trivial divisor of $z$.

[End of Conjecture C3 (proven false)]

Update: Nov 2, 2020

I found an interesting linkage between $\lfloor {z \over r} \rfloor + r$ and the Digital Root of a number defined in terms of the floor function. The digial root of an integer $n$ in base $b$ is denoted by $dr_b(n)$

$$dr_b(n) = {n - (b-1)\bigg\lfloor {n - 1 \over b - 1} \bigg\rfloor}$$

So,

$$n = dr_b(n) + {(b-1)\bigg\lfloor {n - 1 \over b - 1} \bigg\rfloor}$$

Choosing $n - 1 = z, b - 1 = r$, we get

$$z + 1 = dr_{r+1}(z + 1) + {r\bigg\lfloor {z \over r} \bigg\rfloor}$$

Adding $r^2$ both sides,

$$z + 1 + r^2 = dr_{r+1}(z + 1) + {r\bigg\lfloor {z \over r} \bigg\rfloor} + r^2$$

$$z + 1 - dr_{r+1}(z + 1) + r^2 = {r\bigg(\bigg\lfloor {z \over r} \bigg\rfloor + r\bigg)}$$

$$\implies \bigg\lfloor {z \over r} \bigg\rfloor + r = {z + 1 - dr_{r+1}(z + 1) + r^2 \over r}$$

Also observe that

$$z = (dr_{r+1}(z + 1) - 1) + {r\bigg\lfloor {z \over r} \bigg\rfloor}$$

$$\implies z \equiv (dr_{r+1}(z + 1) - 1) \mod r$$

If $r$ is a factor of $z$ then

$$z \equiv 0 \equiv (dr_{r+1}(z + 1) - 1) \mod r$$

$$\implies dr_{r+1}(z + 1) \equiv 1 \mod r$$

This might be an interesting lead to pursue as there is probably a recurrence relation we can form between digital roots in successive bases $r$ and $r+1$ or $r+1$ and $r-k$ that helps recover $r-k$ as a factor that gets $z \mod (r-k) \equiv 0$.

Solution 1:

This answer proves the following claims :

Claim 1 : $$\min\bigg(\left\lfloor\dfrac{z}{r}\right\rfloor+r\bigg)=\begin{cases}2\lfloor{\sqrt z}\rfloor&\text{if $\{\sqrt z\}\lt\frac 12$ and $\lfloor \sqrt z\rfloor\gt\dfrac{\{\sqrt z\}^2}{1-2\{\sqrt z\}}$} \\\\2\lfloor{\sqrt z}\rfloor+1&\text{otherwise} \end{cases}$$ where $\{x\}$ denotes the fractional part of $x$.

Claim 2 : Conjecture C1 is true.

Claim 1 : $$\min\bigg(\left\lfloor\dfrac{z}{r}\right\rfloor+r\bigg)=\begin{cases}2\lfloor{\sqrt z}\rfloor&\text{if $\{\sqrt z\}\lt\frac 12$ and $\lfloor \sqrt z\rfloor\gt\dfrac{\{\sqrt z\}^2}{1-2\{\sqrt z\}}$} \\\\2\lfloor{\sqrt z}\rfloor+1&\text{otherwise} \end{cases}$$ where $\{x\}$ denotes the fractional part of $x$.

Proof :

Using that $x-1\lt \lfloor x\rfloor \le x$ and AM-GM inequality, we have $$\min\bigg(\left\lfloor\dfrac{z}{r}\right\rfloor+r\bigg)=\left\lfloor\dfrac{z}{r_m}\right\rfloor+r_m\gt \frac{z}{r_m}+r_m-1\ge 2\sqrt{z}-1\tag1$$

Also, if $\sqrt{z}=n+a$ where $n\in\mathbb Z$ and $0\le a\lt 1$, we have $$\begin{align}\left\lfloor\dfrac{z}{\lfloor \sqrt z\rfloor+1}\right\rfloor+\lfloor \sqrt z\rfloor+1&=\left\lfloor\dfrac{n^2+2an+a^2}{n+1}\right\rfloor+n+1 \\\\&=\left\lfloor n+2a-1+\frac{(1-a)^2}{n+1}\right\rfloor+n+1 \\\\&=2\lfloor\sqrt z\rfloor+\left\lfloor 2a+\frac{(1-a)^2}{n+1}\right\rfloor\end{align}$$

We can say that $2a+\frac{(1-a)^2}{n+1}\lt 2$ always holds since $$2a+\frac{(1-a)^2}{n+1}\ge 2\implies \frac{(1-a)^2}{n+1}\ge 2(1-a)\implies \frac{1-a}{n+1}\ge 2\implies -a\ge 2n+1$$which is impossible.

Case 1 : If $a\lt \frac 12$ and $n\gt\frac{a^2}{1-2a}$, then we have $$(2\sqrt z-1)-(2\lfloor\sqrt z\rfloor-1)=2n+2a-1-2n+1=2a\ge 0\implies 2\sqrt z-1\ge 2\lfloor\sqrt z\rfloor-1$$ and $$(2\sqrt z-1)-2\lfloor\sqrt z\rfloor=2a-1\lt 0\implies 2\sqrt z-1\lt 2\lfloor\sqrt z\rfloor$$ and $$2a+\frac{(1-a)^2}{n+1}\lt 1\iff 2an+2a+1-2a+a^2\lt n+1\iff n\gt\frac{a^2}{1-2a}$$

So, in this case, it follows from $(1)$ that $$\min\bigg(\left\lfloor\dfrac{z}{r}\right\rfloor+r\bigg)=\left\lfloor\dfrac{z}{\lfloor \sqrt z\rfloor+1}\right\rfloor+\lfloor \sqrt z\rfloor+1=2\lfloor{\sqrt z}\rfloor$$

Case 2 : If $a\lt \frac 12$ and $n\le\frac{a^2}{1-2a}$ ($\iff n\le 2an+a^2$), then we have $$(2\sqrt z-1)-(2\lfloor\sqrt z\rfloor-1)=2a\ge 0\implies 2\sqrt z-1\ge 2\lfloor\sqrt z\rfloor-1$$ and $$(2\sqrt z-1)-2\lfloor\sqrt z\rfloor=2a-1\lt 0\implies 2\sqrt z-1\lt 2\lfloor\sqrt z\rfloor$$ and $$2a+\frac{(1-a)^2}{n+1}\ge 1\iff 2an+2a+1-2a+a^2\ge n+1\iff n\le\frac{a^2}{1-2a}$$

For any integer $c$, we have $$\left\lfloor\dfrac{z}{\lfloor \sqrt z\rfloor+c}\right\rfloor+\lfloor \sqrt z\rfloor+c=\left\lfloor\dfrac{n^2+2an+a^2}{n+c}\right\rfloor+n+c=2n+\left\lfloor 2a+\frac{(a-c)^2}{n+c}\right\rfloor$$

Here, suppose that $$2a+\frac{(a-c)^2}{n+c}\lt 1$$ Then, we have $$2an+2ac+a^2-2ac+c^2\lt n+c\implies 2an+a^2\lt n+c-c^2$$ $$\implies n\le 2an+a^2\lt n+c-c^2\implies n\lt n+c-c^2\implies c(c-1)\lt 0$$ which contradicts that $c$ is an integer.

So, we see that if $a\lt \frac 12$ and $n\le\frac{a^2}{1-2a}$, then there is no $r$ such that $\lfloor\frac zr\rfloor+r=2\lfloor\sqrt z\rfloor$.

So, in this case, it follows from $(1)$ that $$\min\bigg(\left\lfloor\dfrac{z}{r}\right\rfloor+r\bigg)=\left\lfloor\dfrac{z}{\lfloor \sqrt z\rfloor+1}\right\rfloor+\lfloor \sqrt z\rfloor+1=2\lfloor{\sqrt z}\rfloor+1$$

Case 3 : If $a\ge \frac 12$, then we have $$(2\sqrt z-1)-2\lfloor\sqrt z\rfloor=2a-1\ge 0\implies 2\sqrt z-1\ge 2\lfloor\sqrt z\rfloor$$ and $$(2\sqrt z-1)-(2\lfloor\sqrt z\rfloor+1)=2(a-1)\lt 0\implies 2\sqrt z-1\lt 2\lfloor\sqrt z\rfloor+1$$ and $$2a+\frac{(1-a)^2}{n+1}\ge 1\iff 2an+2a+1-2a+a^2\ge n+1\iff a^2\ge \underbrace{(1-2a)}_{\le 0}n$$which always holds.

So, in this case, it follows from $(1)$ that $$\min\bigg(\left\lfloor\dfrac{z}{r}\right\rfloor+r\bigg)=\left\lfloor\dfrac{z}{\lfloor \sqrt z\rfloor+1}\right\rfloor+\lfloor \sqrt z\rfloor+1=2\lfloor{\sqrt z}\rfloor+1.\quad\blacksquare$$

Claim 2 : Conjecture C1 is true.

Proof :

We may suppose that $3\le a\le \sqrt z$ from which we have $$3\le a\le z\implies (3a-z)(a-3)\le 0\implies 3a^2+3z\le az+9a\implies a+\frac za\le \frac z3+3$$ we get $$a+b=a+\frac za\le \frac z3+3\tag2$$

It follows from Claim 1 that $$-\min\bigg(\left\lfloor\frac zr\right\rfloor+r\bigg)\le -2\lfloor\sqrt z\rfloor\tag3$$

Finally, from $(2)(3)$, we have $$(a+b)-\min\bigg(\left\lfloor\frac zr\right\rfloor+r\bigg)\le \frac z3-2\lfloor\sqrt z\rfloor+3.\quad\blacksquare$$