# 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
• Further insight: If you find a prime factor $p$, it's totally legitimate to just return it and not worry about the cofactor. Partial factorization algorithms like ECM are definitely useful, and in the case of semiprimes they solve the problem completely. Indeed, if you find a composite 1 < m < n, that's useful too, even without having any more factors. Apr 13 at 15:19

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.