What's the runtime of this method and is this method correct?

Question

Let $n=pq$ be the prime decomposition. I am searching for $l$ such that there exists a $k$ with:

$$n^l = a \cdot 2^k + b$$ and $$ 1 < \gcd(b,n^l) < n^l$$

Edit by comment of @GerryMyerson: If $n^l = a 2^k +b = \sum_{i=0} ^r n_i 2^i$, then we require, that $b$ will be the last digits of $n^l$, hence: $$b = \sum_{i=0}^{k-1} n_i 2^i$$ Then necessarily: $$a = \sum_{i=k}^r n_i 2^{i-k}$$

Here is an example of what I mean: $$n = 3 \cdot 7 = 10101_2$$ For $l=1$ we do not find $b$. Let us look at $l=2$: Then $$n^2 = 110111001_2$$ Taking $b=3^2 = 1001_2$ which are the last digits of $n^2$, we find that $a=27=11011_2$, which are the first digits of $n^2$. This coincides with what @GerryMyerson suggested, but in general this will not be the case.

It is to me not clear that such an $l$ will exist, and how big $l$ will be compared to $\log(n)$. So if you have any idea in this direction, that would be nice.

Having such a $g=\gcd(b,n^l)$ and hoping it will be of the form $p^rq^s$ with $s \neq r$, we might divide it successively through $n$ until $g = q^m$ is a prime power, so that we have $g=q^m$ for some $m$. Recognizing this as a prime power (which can be done fast), we can compute $q$ a divisor of $n$.

I think that the running time, if the method is correct, will be $1 \le l \le t$, $\frac{t(t+1)(2t+1)}{6} \log(n)^2 = \log(n)^2 \sum_{l=1}^t l^2 = \log(n^1)^2+\log(n^2)^2+\cdots \log(n^t)^2$. Explanation: For each $l=1,\cdots,t$ we have $\log(n^l)$ digits. For each digit we compute a $\gcd(n^l,x)$ which takes time on average $\log(n^l)$.

If one can prove that $t \le \log(n)^c$, for example $t \le \log(n)^2$, then one would have a fast method to find the divisors of $n$.

It would be nice, if a better analysis of the running time is available: Here is the SAGEMATH code:

n = next_prime(randint(1,10^2))*next_prime(randint(1,10^3))
b = 2
a1 = n
ex = 0
steps = 0
g = 2*n
print log(n).N()**5
while (not is_prime_power(g)) and ex < log(n)^2:
    ex += 1
    N = n**ex
    d = N.digits(b)
    d1 = []
    d2 = [x for x in d]
    a1 = 0
    for k in xrange(1,len(d)):
        steps += 1
        bit = d2.pop(0)
        d1.append(bit)
        #D1 = d[0:k]
        #D2 = d[k:]
        #print d1==D1 
        a1 = a1+bit*2**(k-1)
        #a2 = (n**ex-a1)/2**(len(d1))
        #A1 = sum([d1[i]*2**i for i in range(len(d1))])
        #A2 = sum([d2[i]*2**i for i in range(len(d2))])
        #print a1,a2,n**ex == A1+2**k*A2,A1,A2
        print steps, steps/log(n).N()^5
        if 1 < gcd(N,a1) < N:
            g = gcd(n**ex,a1)
            print ">",g
            while not is_prime_power(g):
                g = g/n
            print is_prime_power(g,get_data=True)
            print ex,log(n).N(),steps
            break

Edit I did some experiments with primes up to $1000$ and here is the result (indicating that it can for those primes be done with $t \le \log(n)^2$:

def method(n,T):
    steps = 0
    g = 2*n
    N= 1
    ex = 0
    while (not (1 < g < n) ) and ex <= T:
        ex += 1
        N = N*n
        d = N.digits(2)
        d1 = []
        d2 = [x for x in d]
        a1 = 0
        for k in xrange(1,len(d)):
            bit = d2.pop(0)
            d1.append(bit)
            a1 = a1+bit*2**(k-1)
            steps += 1 
            g = gcd(N,a1)
            if 1 < g < N:
                if floor(log(g)/log(n)).N()==(log(g)/log(n)).N():
                    break
                while not is_prime_power(g):
                    g = Integer(g/n)
                p,r =  is_prime_power(g,get_data=True)
                if n%p ==0 and is_prime(p):
                    return p,ex,k,steps
    return None

for p in primes(3,1000):
    for q in primes(p+1,1000):
        n = p*q
        x = method(n,T=log(n)^2)
        if x is None:
            print p,q

If we set $T = \log(n)$ then the method will not work in this time for some numbers: For example: $n= 19 \cdot 43$. However with $T=\log(n)^2$ the method works for these numbers.

Answer 1

Assuming $p$ and $q$ are odd primes, an $l$ always exists where

$$n^l = a \cdot 2^k + b \tag{1}\label{eq1}$$

with $1 \lt \gcd(b,n^l) \lt n^l$, $a \gt 0$, and the condition implied later of $b \lt 2^k$. However, showing there exists a $b = p^r q^s$ with $r \ne s$ is more problematic & less assured.

First, consider $b = n^d$ for some integer $d \ge 1$, and choose the smallest $k$ allowed, i.e., $k = \lceil \log_2(b) \rceil$. For some $l \gt d$, \eqref{eq1} now becomes

$$n^l = a \cdot 2^k + n^d \implies n^d\left(n^{l-d} - 1\right) = a \cdot 2^k \tag{2}\label{eq2}$$

Since $\gcd\left(n^d, 2^k\right) = 1$, this means

$$n^{l-d} \equiv 1 \pmod{2^k} \tag{3}\label{eq3}$$

There always exists an $l - d$, with the smallest one being the multiplicative order, i.e., $\operatorname{ord}_{2^k}\left(n\right)$, with this also always being a factor of, & thus $\le$, Euler's totient function, i.e., $\varphi\left(2^k\right) = 2^{k-1}$. In general, especially for large $n$, the multiplicative order will be considerably bigger than $\log(n)$, and even $\log(n)^c$ where $c = \log(n)^2$.

A basic example with $d = 1$ and $n = 3 \times 7 = 21$ gives $k = 5$ and $2^k = 32$. In this case, the multiplicative order is $8$ giving $l = 9$. Thus, $a = \frac{21^9 - 21}{32} = 24821251455$ so, in binary, $b^l = 21^9 = 794280046581 = 1011100011101110110001111010111111110101_2$, $a \times 2^k = 24821251455 \times 32 = 1011100011101110110001111010111111100000_2$ and $b = 21 = 10101_2$. The bottom $5$ digits of $b^l$ are the same as $b$ of $10101_2$.

Next, consider $b = p^r q^s$, for some non-negative integers $r$ and $s$ with $r \ne s$. Once again, choose the smallest $k$ allowed, i.e., $k = \lceil \log_2(b) \rceil$. For some $l \ge \max(r, s)$, \eqref{eq1} becomes

$$n^l = a \cdot 2^k + p^r q^s \implies p^r q^s\left(p^{l-r}q^{l-s} - 1\right) = a \cdot 2^k \tag{4}\label{eq4}$$

As before, since $\gcd\left(p^r q^s,2^k\right) = 1$, this means

$$p^{l-r}q^{l-s} \equiv 1 \pmod{2^k} \tag{5}\label{eq5}$$

Next, let

$$e = \operatorname{ord}_{2^k}(p), \; f = \operatorname{ord}_{2^k}(q), \; g = |r - s| \tag{6}\label{eq6}$$

An $l$ exists so \eqref{eq5} is true if at least one of the following conditions holds:

---

Condition #1: In \eqref{eq5}, $l - r$ and $l - s$ are integral multiples of $e$ and $f$, respectively, i.e.,

$$m_1(e) = l - r \tag{7}\label{eq7}$$

$$m_2(f) = l - s \tag{8}\label{eq8}$$

Thus, \eqref{eq7} minus \eqref{eq8} gives

$$m_1(e) - m_2(f) = s - r \tag{9}\label{eq9}$$

Bézout's identity states there are solutions $m_1$ and $m_2$ for \eqref{eq9} iff $\gcd(e, f) \mid g$. Among the infinite number of solutions, you can choose any which give non-negative values for $m_1$ and $m_2$ and, thus, $l$ being large enough.

---

Condition #2: $\operatorname{ord}_{2^k}(pq)$ has non-zero remainders when divided by $e$ and $f$ of $1 \le h \lt e$ and $1 \le i \lt f$, respectively. This results in

$$p^{h}q^{i} \equiv 1 \pmod{2^{k}} \tag{10}\label{eq10}$$

The most general case is to take this to any integral power $m_3$ and then multiply by integral powers $m_4$ of $p^e$ and $m_5$ of $q^f$ to get

$$p^{m_3(h) + m_4(e)}q^{m_3(i) + m_5(f)} \equiv 1 \pmod{2^{k}} \tag{11}\label{eq11}$$

Equating $l - r$ and $l - s$ from \eqref{eq5} to those powers gives

$$m_3(h) + m_4(e) = l - r \tag{12}\label{eq12}$$

$$m_3(i) + m_5(f) = l - s \tag{13}\label{eq13}$$

Next, \eqref{eq12} minus \eqref{eq13} gives

$$m_3(h - i) + m_4(e) - m_5(f) = s - r \tag{14}\label{eq14}$$

As before, Bézout's identity states there are solutions $m_3$, $m_4$ and $m_5$ for \eqref{eq14} iff $\gcd(h - i, e, f) \mid g$. Among the infinite number of solutions, you can choose any which give non-negative values for $m_3$, $m_4$ and $m_5$ so $l$ will be large enough.

---

For large $p$ and $q$, since $e$ and $f$ will be much smaller than $k$, the conditions above, especially condition #1, will not hold very often. I don't know for sure, but I suspect there are some $n$ with no such $l$ and, if so, then it'll likely fail more often as $p$ and $q$ become very large. However, even when an $l$ does exist, it'll likely again usually be relatively big compared to $\log(n)^c$.

Regarding the run time of your SAGEMATH code, I don't know much about the speed of the various operations, but I suspect you're correct the "gcd(N,a1)" in the line

if 1 < gcd(N,a1) < N:

is likely the main bottleneck. If this takes on average an order of $\log\left(n^l\right)$ time, then your calculated running time should be a reasonable estimate.

I realize the code you've provided has not been optimized very much, with most such optimization requiring more code, variables, etc., but there's at least one simple thing you can do without adding any code. In "g = gcd(n**ex,a1)", replace "n**ex" with "N" since it's not changed after it's assigned to be "n**ex" and, in fact, "N" is used just in the line above it. Although a good optimizing compiler or interpreter may handle this for you, I suggest you don't rely on this happening.