Integers divisible by $2^k$ where $\sqrt z \le 2^k{\beta} \le z$ and Integer Factoring
Background
This subproblem occurs in the analysis of the Egyptian Multiplication method. I am not analyzing the multiplication method per se, but using it in reverse to see if we can come up with an Integer Factoring method. Here's a short description of the Egyptian Multiplication method with an example.
If we want to multiply two numbers, we list them down under headings $a, b$ as shown in the table. The entry in column a are quotients after repeated division by 2. Eventually, we stop when $a = 1$. The remainder $a \mod 2$ from each step is written in column $r$. In column $b$, we repeatedly double the previous entry and write it down. The column $p$ is the positional value. Note that column $r$ is the binary representation of $a = 23 = (10111)_2$. This can be seen in column $r*p$ which sums up to $23$, the value of $a$. Finally, $r*b$ in the last column adds up to the answer, $a*b = 1633$.
Knowing this method, let us try to reverse it to attempt factoring 1633. I am calling it the Reverse Egyptian Factor search. Here is a naive first iteration.
Our objective is to identify the number 1136 which when divided by 2, $k$ times gives the factor.
In the general case, we will assume that the number we want to factor is odd. If it is not, we can always divide it by 2 repeatedly to obtain $2^{\alpha}{\beta}$ where ${\beta}$ is odd and use this method to factor ${\beta}$. In the current example, 1633 is odd. So, we can proceed.
Note that the result of doubling a number repeatedly is a number of the form $2^{k}t$. Also, note that a number $z = ab$ can be partially factored into $a$ and $b$, where one of the partial factors is $\le \sqrt z$ and the other is $\ge \sqrt z$. Without loss of generality, assume that we are doubling the larger factor $b$ in the search process. This means $k$ is bounded by $\lfloor \log_2(z)/2 \rfloor$.
So, we need a number of the form $\sqrt z \le 2^k{\beta} \le z$. A naive search would check all even numbers, but we can do better. Noting that $\sqrt z \le 2^k{\beta} \le z$, we can solve for the range of $k$. This is where the question of the type asked at the start of this article was posed.
Here's what happens when we choose a number that is not the right choice. We started with 1632 and after $k$ steps of division (reversing the doubling), we end with $102$. We expect to end the halving in $k$ or less steps. We know that the factor cannot be 102 because we have reached $k$ steps and it is even. We can also check it by dividing 1633 by 102. $102 \nmid 1633$.
So, lets continue the naive search with the next even number, 1630.
Here, we get 815, an odd number in just one division and $815 \nmid 1633$.
Questions
- Can we apply any tricks to make this search smarter and faster, knowing that
$$k \in [2, {\log_2 z \over 2}], \sqrt z \le 2^k{\beta} \le z$$
- We can also do this method with multiplying and dividing by other primes $\{ 3, 5, 7, \dots \}$. Does that allow us to sieve and determine ${ \beta }$?