<p>It's not cheating.  The last step of an algorithm can certainly be: compute <span class="math-container">$n/p_1$</span> and check whether that is an integer and is prime.  That's an allowable step in an algorithm and can be computed efficiently.</p>
<p>RSA challenges allow you to do whatever you want to obtain a factorization, as long as you can implement it and it finishes running and gives you a result.</p>

CC BY-SA 4.0
2022-07-11T18:09:06.580Z
Makes sense, thank you!
Würthi
CC BY-SA 4.0
2022-07-11T18:07:21.800Z
2022-07-11T18:07:21.800Z
D.W.
<p>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,<span class="math-container">$\space n=p_1p_2$</span>. 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 <span class="math-container">$p_1$</span> whether the <span class="math-container">$n$</span> contains a <span class="math-container">$p_2$</span> such that <span class="math-container">$p_2= \frac{n}{p_1}$</span> and terminating if it is so?</p>
<p>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?</p>

CC BY-SA 4.0
2022-07-11T16:54:28.980Z
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.
CC BY-SA 4.0
2022-07-11T16:59:18.740Z
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$).
Neal Young
CC BY-SA 4.0
2022-07-11T17:01:48.843Z
Edited, thanks!
Würthi
CC BY-SA 4.0
2023-04-13T15:19:40.533Z
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.
Charles
<ds.algorithms><factoring><primes>
Would the following be an acceptable part of an algorithm if used for prime factorization
Würthi
# Would the following be an acceptable part of an algorithm if used for prime factorization

(Asked by: username_0 on 2022-07-11)

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?

**Tags:** ds.algorithms, factoring, primes

> **Comments:**
> **username_1**: 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?  
> **username_2**: 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$).  
> **username_0**: Edited, thanks!  
> **username_3**: 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.  

---

## 1 answers

### Answer by username_1 on 2022-07-11. Score: 2 | Accepted answer

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.

RSA challenges allow you to do whatever you want to obtain a factorization, as long as you can implement it and it finishes running and gives you a result.

> **Comments:**
> **username_0**: Makes sense, thank you!  

---

