# Would the following be an acceptable part of an algorithm if used for prime factorization

Suppose I have some super fancy algorithm for prime factorization. I want to demonstrate its potential on a difficult case, like an RSA sized number composed of two primes,$$\space n=p_1p_2$$. As far as I know, 2-factor primes are considered to be most difficult. I want to demonstrate that it performs in a good runtime. Would it be considered cheating to hard code into the algorithm an expression that checks immediately after finding $$p_1$$ whether the $$n$$ contains a $$p_2$$ such that $$p_2= \frac{n}{p_1}$$ and terminating if it is so?

Would this be okay for demonstration purposes? Would it fly in an RSA challenge? Is a provision for such difficult cases a faux-pas in algorithm design?

• What do you mean by "differ by one bit"? Do you mean their length differs by one bit, or the binary representations of p and q has Hamming distance 1? Please edit your question to clarify what you are asking?
– D.W.
Jul 11, 2022 at 16:54
• If you know one prime factor $p_1$ of $n$, and you know $n$ has just two prime factors, then you can very quickly compute the second prime factor $p_2$ using $p_2 = n/p_1$. So, once an algorithm finds $p_1$ in this context, it is essentially done (it has the full factorization of $n$). Jul 11, 2022 at 16:59
• Edited, thanks! Jul 11, 2022 at 17:01

It's not cheating. The last step of an algorithm can certainly be: compute $$n/p_1$$ and check whether that is an integer and is prime. That's an allowable step in an algorithm and can be computed efficiently.