# Finding the time complexity of a prime factorization algorithm

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 $$$$A - \frac{B^2+B}{2} + \frac{n^2+n}{2} = D \tag{1}$$$$ 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.

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.

• I’m voting to close this question because this site is not suited for restricted information. Jan 1 at 11:15
• The problem of integer factorization has been and is still a topic of much interest in the CS community and has been investigated by many competent people. An elementary solution is vey very unlikely. Jan 1 at 11:40
• I am sorry to read this. Jan 1 at 15:52
• You are on a wrong track (I don't mean about this paper, I mean about how to behave on this site). Jan 1 at 16:29
• What exactly is your question? I don't see a question here. We are a question-and-answer site, so we require you to articulate a specific, answerable question. Also, opinions are off-topic here. A request for "Any kind of advice or opinion" is too open-ended to be a good fit here. Please edit your post to ask a specific question.
– D.W.
Jan 1 at 21:33

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).