Finding the time complexity of a prime factorization algorithm

Question

In this question, I'm going to introduce a prime factorization algorithm which I'm working on as my personal project.

I may attach a Python code to introduce the algorithm. If it contravenes the rule please let me know, I will consider it editing as a pseudo-code or substitute it with some link.

import timeit
import gmpy2
import math

A = gmpy2.mpz(11111111111)
# Input a positive integer to factor.
# Put it inside the parentheses as "A = gmpy2.mpz(....)"

def factor(A):
    B = gmpy2.mpz(math.sqrt(2 * A + 0.25) - 1)
    D = gmpy2.mpz(A - (B * B + B) / 2)
    while (D > 0):
        B += 1
        D = gmpy2.mpz(A - (B * B + B) / 2)
    n = gmpy2.mpz(0)
    while (D != 0 and B <= A):
        if (D > 0):
            B += 1
            D -= B
        else:
            n += 1
            D += n
    if B > A:
        return output(0, 0, 0)
    else:
        if (B - n) % 2 == 0:
            E = gmpy2.mpz((B - n) / 2)
            F = gmpy2.mpz(B + n + 1)
        else:
            E = gmpy2.mpz(B - n)
            F = gmpy2.mpz((B + n + 1) / 2)
        return output(A, E, F)


def output(A, E, F):
    if A == 0:
        print(f"Initial Value Error: Reset the B value")
    else:
        if A % E != 0 or A % F != 0 or A != E * F:
            print(f"[Error Occurred]  {A}  !=  {E}  *  {F}")
        else:
            print(f"{A}  =  {E}  *  {F}")
    return 0


if __name__ == '__main__':
    if A >= 2:
        timer_start = timeit.default_timer()
        factor(A)
        timer_stop = timeit.default_timer()
        running_time = round(timer_stop - timer_start, 6)
        print("running time: ", running_time, " seconds")
    else:
        print("undefined for A<2")

As I said, the code is a part of the personal project which I'm working on. So the theoretical explanation of the code can't be introduced in detail as of now. However, I may try to summarize the overview of the theory behind as follows.

Any positive integer $A$ can be represented as $A = a \times b$. When we think about $a \times b$, where $b \neq 1$, we can notice that it can be alternatively represented as $$ A = \cdots (a-2) + (a-1) + a + (a+1) + (a+2) +\cdots $$ when A is odd $$ A = \cdots (a-2) + (a-1) + (a+1) + (a+2) \cdots $$ when A is even.

The mechanism of this algorithm aims to find the value of $B$ and $n$ of the following equation \begin{equation} A - \frac{B^2+B}{2} + \frac{n^2+n}{2} = D \tag{1}\end{equation} for when $D=0$.

If we manipulate the equations by subtracting and adding summation of positive integers

$$\begin{aligned} A - \frac{B^2+B}{2} + \frac{n^2+n}{2} &= [\cdots (a-2) + (a-1) + a + (a+1) + (a+2) +\cdots] \\&\hspace{7mm}- [u + (u+1) + (u+2) \cdots] + [1 + 2 + 3 \cdots + n] \\&= 0 \end{aligned}$$

we can observe a property as follows $$ A = \frac{(B-n)(B+n+1)}{2} $$

Among the numerous cases of $ A = a \times b$, only $A \in $ {prime number} $\bigcup$ {perfect power of 2} are represented as $A = 1 \times A$. The reason for a prime number being represented as $A = 1 \times A$ is obvious. The reason for the case when $A$ is a perfect power of 2, $2^e$ can be represented only as a multiplication between powers of 2, which are all even, unless $2^e = 1 \times 2^e$.

The procedure of algorithm repeats the addition and subtraction of positive integers which let the value of D (the RHS of equation (1)) to oscillate between 0, until it reaches 0. So the longest expected computation time for the algorithm of $A$ is the case when $A$ is represented as $$A = \frac{[A-(A-1)][A+(A-1)+1]}{2}$$ or $$A = \frac{[(\frac{A-1}{2}+1)-(\frac{A-1}{2}-1)][(\frac{A-1}{2}+1)+(\frac{A-1}{2}-1)+1]}{2}$$

The fact that $2^e$ can be only represented as $2^e = 1 \times 2^e$, particularly as $$2^e = \frac{[2^e - (2^e-1)][2^e + (2^e - 1)+1]}{2}$$ gives us a good tool to assume the time complexity.

In my numerical experiments, the computation time for $2^e$ doubles every time as $e$ gets larger by 1. Furthermore, I've observed that the computation time of every other $A$'s of which $A < 2^e$ are less than the computation time of $2^e$.

By this observation, I'm assuming that the time complexity of this algorithm is not bad, somewhat, no more than sub-exponential time. However, I'm not an expert nor experienced with evaluating the time complexity of algorithms. If I observe some profiles and answers from some named users, I see that there are lots of experts who have experiences in those fields. So I'm here to ask for some advice.

Any kind of advice or opinion would be grateful. Looking forward to an honest opinion via comments and answers. Thank you.

[Edit]

I wanted to engage on discussion as much as I can. However, because of some unfriendly behavior which I encountered at the comment section of here, I concluded that Stackexchange community might not be the right place to bring up a post like mine.

I also respect all the points made by moderator. Still, I may not endeavor to delete this post by myself since some number of people have already encountered it. So just leaving the post as it was, I may not engage on further discussion unless definitely required.

You may feel free to test and modify this code without noticing me.

Answer 1

I didn't read the details of how your code functions, so I won't comment on your algorithm. However, the code itself seems to have a time complexity of O(sqrt(A)). As A becomes very large, B approaches sqrt(2A), making D approach -sqrt(2A). Then, your second while loop seems to have a time complexity of O(B), as the statement n <= B+1 must always be true in your code, and n is incremented with a constant step up to B. However, if your code reaches the point where n = B, then your code will continually add or subtract 1 every two iterations (depending on the starting values of B and D) from D until D == 0, adding O(|D|) to the complexity. Thus, your algorithm in total has a complexity of around O(B)+O(|D|), which can be simplified to O(sqrt(A)). So, your algorithm has similar runtime complexity to a classic brute-force algorithm looping from 1 to sqrt(A), although the constant factor may vary greatly (I don't think I'm qualified to state which algorithm has a better constant factor in the worst case).

Disclaimer: I am not an expert in CS research, I'm a competitive programmer, and thus I only know how to make basic estimates of runtime.

Hope this helps somewhat. Good luck with your project!

Answer 2

I’d suggest running your algorithm and comparing its runtime to the trivial trial division algorithm. (Try dividing by 2, 3, followed by 6K-1 and 6K+1 until the square of the divisor exceeds the remaining number).

Try especially the behaviour for products of two or three large primes or for primes or numbers like 2^30 with many factors.

PS it looks very similar to the Fermat algorithm, which is quite fast for factors close to sqrt(a) but awfully bad if you have one tiny and one large factor. So try this fror a 12 digit prime multiplied by 3, 5 or 7.